On approximating planar metrics by tree metrics.

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)

zbMATH Keywords

MetricsAlgorithmsCombinatorial problemsPlanar graphsProbabilistic approximationsTree metrics

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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.