Lower-Stretch Spanning Trees

DOI10.1137/050641661zbMath1172.68045OpenAlexW2569942321MaRDI 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 treeslow-distortion embeddingsprobabilistic tree metrics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Unnamed Item ⋮ Spanners of bounded degree graphs ⋮ Minimum spanning tree cycle intersection problem on outerplanar graphs ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ Unnamed Item ⋮ 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 ⋮ Spanners in sparse graphs ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ The DFS Fused Lasso: Linear-Time Denoising over General Graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Integral cycle bases for cyclic timetabling ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ Approximating fault-tolerant group-Steiner problems ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ 2-node-connectivity network design

This page was built for publication: Lower-Stretch Spanning Trees