Eccentricity-approximating trees in chordal graphs
type: Item
instance of: scholarly article
title: Eccentricity-approximating trees in chordal graphs
zbMATH Open document ID: 0946.05024
DOI: 10.1016/S0012-365X(00)00030-3
author: Erich Prisner
published in: Discrete Mathematics
publication date: 2000-10-18T00:00:00Z
review text: The eccentricity of a vertex \(v\) of a graph is the maximum distance of \(v\) to any other vertex in the graph. A spanning tree \(T\) of a connected graph \(G\) is called eccentricity \(k\)-approximating when for every vertex \(v\), the difference of the eccentricity of \(v\) in \(T\) and the eccentricity of \(v\) in \(G\) is at most \(k\). This paper shows that every chordal graph has an eccentricity 2-approximating spanning tree.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1462289
zbMATH Keywords: spanning trees
zbMATH Keywords: chordal graphs
zbMATH Keywords: eccentricity
zbMATH Keywords: tree spanners
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1462289