Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
- 23 November 2011
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 47 (1) , 187-214
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted GraphsSIAM Journal on Computing, 2009
- Ordinal Embedding: Approximation Algorithms and Dimensionality ReductionLecture Notes in Computer Science, 2008
- Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphsElectronic Notes in Discrete Mathematics, 2008
- Spanners for bounded tree-length graphsTheoretical Computer Science, 2007
- Tree-decompositions with bags of small diameterDiscrete Mathematics, 2007
- l∞-Approximation via SubdominantsJournal of Mathematical Psychology, 2000
- A Note on Distance Approximating Trees in GraphsEuropean Journal of Combinatorics, 2000
- Distance Approximating Trees for Chordal and Dually Chordal GraphsJournal of Algorithms, 1999
- Lower Bounds on the Distortion of Embedding Finite Metric Spaces in GraphsDiscrete & Computational Geometry, 1998
- On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)SIAM Journal on Computing, 1998