Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

DOI10.1007/s00454-011-9386-0zbMath1255.68301OpenAlexW3022612511MaRDI QIDQ664543

Ilan Newman, Feodor F. Dragan, Victor Chepoi, Yann Vaxès, Yuri Rabinovich

Publication date: 2 March 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-011-9386-0

zbMATH Keywords

distortiontreesouterplanar graphsapproximation algorithmsmetric embedding

Mathematics Subject Classification ID

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

Related Items (4)

Unnamed Item ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• A note on distance approximating trees in graphs
• \(l_\infty\)-approximation via subdominants.
• Tree-decompositions with bags of small diameter
• Spanners for bounded tree-length graphs
• Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
• Low-distortion embeddings of general metrics into the line
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)

This page was built for publication: Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs