Using petal-decompositions to build a low stretch spanning tree

DOI10.1145/2213977.2214015MaRDI QIDQ5415490zbMATH OpenOpenAlexFDO

Authors Ittai Abraham, Ofer Neiman

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.722.8949

zbMATH Keywords

distortionembeddinglow stretch spanning treemetric spaces

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Using petal-decompositions to build a low stretch spanning tree
• Lower-Stretch Spanning Trees
• Lower-stretch spanning trees
• Distributed algorithms for low stretch spanning trees
• scientific article; zbMATH DE number 2011838

Cited in

(17)

• Duality and nonlinear graph Laplacians
• Engineering a combinatorial Laplacian solver: lessons learned
• Electrical flows over spanning trees
• Covering metric spaces by few trees
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Terminal embeddings
• A Simple Efficient Interior Point Method for Min-Cost Flow
• The DFS fused Lasso: linear-time denoising over general graphs
• Using petal-decompositions to build a low stretch spanning tree
• Density independent algorithms for sparsifying k-step random walks
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Covering Metric Spaces by Few Trees
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
• Steiner shallow-light trees are exponentially lighter than spanning ones
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions

This page was built for publication: Using petal-decompositions to build a low stretch spanning tree

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