Using Petal-Decompositions to Build a Low Stretch Spanning Tree
| Autor: | Ofer Neiman, Ittai Abraham |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Spanning tree General Computer Science Shortest-path tree General Mathematics Induced subgraph 0102 computer and information sciences Minimum spanning tree k-minimum spanning tree Binary logarithm 01 natural sciences Connected dominating set Graph Combinatorics 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Euclidean minimum spanning tree Embedding MathematicsofComputing_DISCRETEMATHEMATICS Minimum degree spanning tree Mathematics |
| Zdroj: | STOC |
| ISSN: | 1095-7111 0097-5397 |
| Popis: | We prove that any graph G=(V,E) with n points and m edges has a spanning tree T such that ∑(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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|