Advertisement
Published in:
2013 | OriginalPaper | Chapter
From Vertex-Telecenters to Subtree-Telecenters
Authors : Zaw Win, Cho Kyi Than
Published in: Facets of Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let T be a tree and v a vertex in T. It is well-known that the branch-weight of v is defined as the maximum number of vertices in the components of T−v and that a vertex of T with the minimum branch-weight is called a vertex-centroid of T. Mitchell (Discrete Math. 24:277–280, 1978) introduced a type of a central vertex called the telephone center or the vertex-telecenter of a tree and showed that v is a vertex-centroid of T if and only if it is a vertex-telecenter of T. In this paper we introduce the notions of the subtree-centroid and the subtree-telecenter of a tree which are natural extensions of the vertex-centroid and the vertex-telecenter, and generalize two theorems of Mitchell (Discrete Math. 24:277–280, 1978) in the extended framework of subtree-centroids and subtree-telecenters. As a consequence of these generalized results we also obtain an efficient solution method which computes a subtree-telecenter of a tree.