Lower-stretch spanning trees
From MaRDI portal
Publication:3581444
DOI10.1145/1060590.1060665zbMath1192.05028MaRDI QIDQ3581444
Shang-Hua Teng, Michael Elkin, Yuval Emek, 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
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, 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, Maximum gradient embeddings and monotone clustering, New length bounds for cycle bases, The zoo of tree spanner problems, Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane