Algorithms for a Core and k-Tree Core of a Tree

✍ Scribed by S.T. Peng; A.B. Stephens; Y. Yesha

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 595 KB
• Volume: 15
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1993.1034

✦ Synopsis

We first give a one-pass algorithm for finding the core of a tree. This algorithm is a refinement of the two-pass algorithm of Morgan and Slater. We then define a generalization of a core which we call a (k)-tree core. Given a tree (T) and parameter (k), a (k)-tree core is a subtree (T^{\prime}) of (T) containing exactly (k) leaves that minimizes (d\left(T^{\prime}\right)=\sum_{v \in V(T)} d\left(v, T^{\prime}\right)), where (d\left(v, T^{\prime}\right)) is the distance from vertex (v) to subtree (T^{\prime}). We then give two algorithms to find a (k)-tree core of a tree with (n) vertices. The complexities of these algorithms are (O(k n)) and (O(n \lg n)), respectively. This work is motivated by a resource allocation problem dealing with a partially replicated distributed database defined on a tree network. This problem is briefly described in the last section of the paper. 1993 Academic Press, Inc.