Lower-stretch spanning trees

DOI10.1145/1060590.1060665MaRDI QIDQ3581444zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Lower-Stretch Spanning Trees
• scientific article; zbMATH DE number 1929927
• scientific article; zbMATH DE number 2011838
• Low-degree minimum spanning trees
• scientific article; zbMATH DE number 7759283
• Spanning tree with lower bound on the degrees
• Spanning trees with low crossing number
• Lower bounds on treespan
• Low-Degree Spanning Trees of Small Weight
• Transforming spanning trees: A lower bound

Cited in

(22)

• Edge-swapping algorithms for the minimum fundamental cycle basis problem
• Transforming spanning trees: A lower bound
• 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 degree spanning trees of small weight
• Low distortion Delaunay embedding of trees in hyperbolic plane
• Lower-Stretch Spanning Trees
• scientific article; zbMATH DE number 2011838 (Why is no real title available?)
• Using petal-decompositions to build a low stretch spanning tree
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Covering Metric Spaces by Few Trees
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Using petal-decompositions to build a low stretch spanning tree
• Local embeddings of metric spaces
• 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

This page was built for publication: Lower-stretch spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581444)