Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Using Petal-Decompositions to Build a Low Stretch Spanning Tree

Ittai Abraham and Ofer Neiman

Abstract

We prove that any graph G=(V,E) with n points and m edges has a spanning tree T such that sum(u,v)∈ E(G)dT(u,v) = O(m log n log log n). Moreover such a tree can be found in time O(m log nlog log n). Our result is obtained using a new petal-decomposition approach which guarantees that the radius of each cluster in the tree is at most 4 times the radius of the induced subgraph of the cluster in the original graph.

Details

Publication typeInproceedings
Published inSTOC
> Publications > Using Petal-Decompositions to Build a Low Stretch Spanning Tree