Lower-stretch spanning trees

DOI10.1145/1060590.1060665zbMath1192.05028OpenAlexW1978086920MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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