TITLE    : Using Petal-Decompositions to Build a Low Stretch Spanning Tree.

AUTHORS  : 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)\in E(G)}d_T(u,v) = O(m \log n \log \log n). 
Moreover such a tree can be found in time O(m \log n\log\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.