Split and Join: Strong Partitions and Universal Steiner Trees for Graphs

Details Split and Join: Strong Partitions and Universal Steiner Trees for Graphs Split and Join: Strong Partitions and Universal Steiner Trees for Graphs

2011-11-21

arxiv.org/abs/1111.4766v3

Computer Science

Data Structures and Algorithms

23 pages

Scientific paper

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph $G$ and a root node $r$, we seek a single spanning tree $T$ of minimum stretch, where the stretch of $T$ is defined to be the maximum ratio, over all subsets of terminals $X$, of the ratio of the cost of the sub-tree $T_X$ that connects $r$ to $X$ to the cost of an optimal Steiner tree connecting $X$ to $r$. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time UST construction for general graphs with $2^{O(\sqrt{\log n})}$-stretch. We also give a polynomial time polylogarithmic-stretch construction for minor-free graphs. One basic building block in our algorithm is a hierarchy of graph partitions, each of which guarantees small strong cluster diameter and bounded local neighbourhood intersections. Our partition hierarchy for minor-free graphs is based on the solution to a cluster aggregation problem that may be of independent interest. To our knowledge, this is the first sub-linear UST result for general graphs, and the first polylogarithmic construction for minor-free graphs.

Affiliated with

Also associated with

No associations

Rating

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs 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 Split and Join: Strong Partitions and Universal Steiner Trees for Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split and Join: Strong Partitions and Universal Steiner Trees for Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376065