A note on distance approximating trees in graphs
type: Item
instance of: scholarly article
title: A note on distance approximating trees in graphs
zbMATH Open document ID: 0958.05046
author: Victor Chepoi
author: Feodor F. Dragan
published in: European Journal of Combinatorics
publication date: 2001-03-30T00:00:00Z
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\).
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1513385
zbMATH Keywords: distance approximation
zbMATH Keywords: tree
MaRDI profile type: Publication
full work available at URL: eujc.1999.0381
OpenAlex ID: W2029803751
cites work: Distance Approximating Trees for Chordal and Dually Chordal Graphs
cites work: Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
DOI: 10.1006/EUJC.1999.0381
description: scientific article; zbMATH DE number 1513385