A note on distance approximating trees in graphs

DOI10.1006/eujc.1999.0381zbMath0958.05046OpenAlexW2029803751MaRDI QIDQ1582482

Feodor F. Dragan, Victor Chepoi

Publication date: 30 March 2001

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/eujc.1999.0381

zbMATH Keywords

treedistance approximation

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (11)

Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ Tree-decompositions with bags of small diameter ⋮ Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs ⋮ Spanners for bounded tree-length graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ A distance approximating trees ⋮ The intrinsic dimensionality of graphs ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle

Cites Work

• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Distance Approximating Trees for Chordal and Dually Chordal Graphs

This page was built for publication: A note on distance approximating trees in graphs