On approximating planar metrics by tree metrics.
From MaRDI portal
Publication:1603386
DOI10.1016/S0020-0190(01)00161-2zbMath1051.68141MaRDI QIDQ1603386
R. Ravi, F. Sibel Salman, Goran Konjevod
Publication date: 14 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (7)
Approximation algorithms for the covering Steiner problem ⋮ Stochastic approximation of lamplighter metrics ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- The geometry of graphs and some of its algorithmic applications
- Aligning sequences via an evolutionary tree
- Extensions of Lipschitz mappings into a Hilbert space
- On Isometric Embeddings of Graphs
- Graph spanners
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Excluded minors, network decomposition, and multicommodity flow
This page was built for publication: On approximating planar metrics by tree metrics.