Lower-stretch spanning trees

DOI10.1145/1060590.1060665zbMath1192.05028MaRDI QIDQ3581444

Michael Elkin, Yuval Emek, Shang-Hua Teng, Daniel A. Spielman

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060665

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Using Petal-Decompositions to Build a Low Stretch Spanning Tree, Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, Covering Metric Spaces by Few Trees, Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion, Local embeddings of metric spaces, Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs, Strong-diameter decompositions of minor free graphs, On the approximability of the minimum strictly fundamental cycle basis problem, Low-light trees, and tight lower bounds for Euclidean spanners, Edge-swapping algorithms for the minimum fundamental cycle basis problem, Engineering a combinatorial Laplacian solver: lessons learned, Maximum gradient embeddings and monotone clustering, Electrical flows over spanning trees, Covering metric spaces by few trees, New length bounds for cycle bases, The zoo of tree spanner problems, Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane