Central Forests in Trees

Details Central Forests in Trees Central Forests in Trees

2008-09-02

arxiv.org/abs/0809.0349v1

Mathematics

Combinatorics

42 pages

Scientific paper

A new 2-parameter family of central structures in trees, called central forests, is introduced. Minieka's $m$-center problem and McMorris's and Reid's central-$k$-tree can be seen as special cases of central forests in trees. A central forest is defined as a forest $F$ of $m$ subtrees of a tree $T$, where each subtree has $k$ nodes, which minimizes the maximum distance between nodes not in $F$ and those in $F$. An $O(n(m+k))$ algorithm to construct such a central forest in trees is presented, where $n$ is the number of nodes in the tree. The algorithm either returns with a central forest, or with the largest $k$ for which a central forest of $m$ subtrees is possible. Some of the elementary properties of central forests are also studied.

Affiliated with

Also associated with

No associations

Rating

Central Forests in Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Central Forests in Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Central Forests in Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-60664