Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
type: Item
instance of: scholarly article
title: Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
zbMATH Open document ID: 1255.68301
author: Victor Chepoi
author: Feodor F. Dragan
author: Ilan Newman
author: Yuri Rabinovich
author: Yann Vaxès
published in: Discrete \& Computational Geometry
publication date: 2012-03-02T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6010844
zbMATH Keywords: metric embedding
zbMATH Keywords: distortion
zbMATH Keywords: trees
zbMATH Keywords: outerplanar graphs
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: s00454-011-9386-0
OpenAlex ID: W3022612511
cites work: On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
cites work: Low-distortion embeddings of general metrics into the line
cites work: Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
cites work: Q2934633
cites work: Distance Approximating Trees for Chordal and Dually Chordal Graphs
cites work: A note on distance approximating trees in graphs
cites work: Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
cites work: \(l_\infty\)-approximation via subdominants.
cites work: Q5315023
cites work: Spanners for bounded tree-length graphs
cites work: Tree-decompositions with bags of small diameter
cites work: Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
cites work: Steiner points in tree metrics don't (really) help
cites work: Lower bounds on the distortion of embedding finite metric spaces in graphs
cites work: Q4792088
DOI: 10.1007/S00454-011-9386-0
description: scientific article; zbMATH DE number 6010844