Using Petal-Decompositions to Build a Low Stretch Spanning Tree

DOI10.1137/17M1115575zbMath1417.68144MaRDI QIDQ4629391

Ittai Abraham, Ofer Neiman

Publication date: 22 March 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

embeddingdistortionspanning treelow stretch

Mathematics Subject Classification ID

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

Related Items

Lossless Prioritized Embeddings ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm for the single source shortest path problem with few distinct positive lengths
• Packing directed circuits fractionally
• Optimum Communication Spanning Trees
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Lower-stretch spanning trees
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Ramsey Spanning Trees and Their Applications
• Solving SDD linear systems in nearly m log ^1/2 n time
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Algorithms – ESA 2004
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Advances in metric embedding theory
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Using Petal-Decompositions to Build a Low Stretch Spanning Tree