Using petal-decompositions to build a low stretch spanning tree

DOI10.1145/2213977.2214015zbMath1286.05028OpenAlexW2072142932MaRDI QIDQ5415490

Ofer Neiman, Ittai Abraham

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

embeddingmetric spacesdistortionlow stretch spanning tree

Mathematics Subject Classification ID

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

Related Items (16)

Covering metric spaces by few trees ⋮ Terminal embeddings ⋮ A Simple Efficient Interior Point Method for Min-Cost Flow ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Duality and nonlinear graph Laplacians ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ The DFS Fused Lasso: Linear-Time Denoising over General Graphs ⋮ Covering Metric Spaces by Few Trees ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ Electrical flows over spanning trees ⋮ Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems

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