Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

DOI10.1007/978-3-642-15369-3_8zbMath1304.68212arXiv1007.0489OpenAlexW2131187309MaRDI QIDQ3588402

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

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.0489

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

This page was built for publication: Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs