Split and join: strong partitions and Universal Steiner trees for graphs

Busch, Costas ; Dutta, Chinmoy ; Radhakrishnan, Jaikumar ; Rajaraman, Rajmohan ; Srinivasagopalan, Srivathsan (2011) Split and join: strong partitions and Universal Steiner trees for graphs Arxiv-eprints . pp. 1-23.

PDF - Author Version

Official URL: http://arxiv.org/pdf/1111.4766


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 TX 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 2O(√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.

Item Type:Article
Source:Copyright of this article belongs to Arxiv Publications.
ID Code:89493
Deposited On:27 Apr 2012 13:48
Last Modified:19 May 2016 04:02

Repository Staff Only: item control page