A note on distance approximating trees in graphs

DOI10.1006/EUJC.1999.0381MaRDI QIDQ1582482zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Feodor F. Dragan

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

distance approximationtree

Mathematics Subject Classification ID

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

Review text

Let \(G\) be a connected simple graph and let \(\lambda\) denote the largest length of some induced simple cycle in \(G\). It is shown how to construct in linear time, for any choice of a vertex \(u\), a tree \(T\) on the same vertex set such that the distance of any vertex to \(u\) is the same in \(G\) as in \(T\), while distances in both graphs between any two vertices do not differ by more than \(\lfloor \lambda/2 \rfloor + \alpha\), with \(\alpha=1\) for all \(\lambda\), except \(4\) and \(5\) where \(\alpha=2\).

Recommendations

• Distance approximating trees in graphs
• A distance approximating trees
• Distance Approximating Trees: Complexity and Algorithms
• Distance approximating spanning trees
• Distance approximating trees for chordal and dually chordal graphs (extended abstract)

Cites work

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

Cited in

(20)

• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• Tree-decompositions with bags of small diameter
• Approximating geodesic tree distance
• Spanners for bounded tree-length graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Characterization of the distance between subtrees of a tree by the associated tight span
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Distance approximating trees in graphs
• Tree-Like Structures in Graphs: A Metric Point of View
• Distance Approximating Trees: Complexity and Algorithms
• scientific article; zbMATH DE number 3991551 (Why is no real title available?)
• Duality between distant point and median of a tree network space
• scientific article; zbMATH DE number 58304 (Why is no real title available?)
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Distance approximating spanning trees
• Notes on diameters, centers, and approximating trees of -hyperbolic geodesic spaces and graphs
• The intrinsic dimensionality of graphs
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• A distance approximating trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582482)