Lower-Stretch Spanning Trees

DOI10.1137/050641661zbMath1172.68045MaRDI QIDQ3624378

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

Publication date: 30 April 2009

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

Full work available at URL: https://doi.org/10.1137/050641661

zbMATH Keywords

low-stretch spanning trees; low-distortion embeddings; probabilistic tree metrics

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The DFS Fused Lasso: Linear-Time Denoising over General Graphs, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, Cycle bases in graphs characterization, algorithms, complexity, and applications, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees, Spanners in sparse graphs, Approximating fault-tolerant group-Steiner problems, Integral cycle bases for cyclic timetabling, Spanners of bounded degree graphs, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, The ordered \(k\)-median problem: surrogate models and approximation algorithms, On notions of distortion and an almost minimum spanning tree with constant average distortion, Mixed-integer programming approaches for the tree \(t^*\)-spanner problem, Terminal embeddings, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs