Lower-stretch spanning trees
From MaRDI portal
Publication:3581444
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
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