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

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

Yuri Rabinovich, Feodor F. Dragan, Yann Vaxès, Victor Chepoi, 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

05C05: Trees

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs