Steiner shallow-light trees are exponentially lighter than spanning ones Academic Article uri icon

abstract

  • For a pair of parameters α,β≥1, a spanning tree T of a weighted undirected n-vertex graph G=(V,E,w) is called an (α,β)-shallow-light tree (shortly, (α,β)-SLT) of G with respect to a designated vertex rt∈V if (1) it approximates all distances from rt to the other vertices up to a factor of α, and (2) its weight is at most β times the weight of the minimum spanning tree MST(G) of G. The parameter α (resp., β) is called the root-distortion (resp., lightness) of the tree T. Shallow-light trees (SLTs) constitute a fundamental graph structure, with numerous theoretical and practical applications. In particular, they were used for constructing spanners in network design, for VLSI-circuit design, for various data gathering and dissemination tasks in wireless and sensor networks, in overlay networks, and in the message-passing model of distributed computing. Tight tradeoffs between the parameters of SLTs were established …

publication date

  • August 4, 2015