An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
type: Item
instance of: scholarly article
title: An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
zbMATH Open document ID: 1481.05029
author: Feodor F. Dragan
published in: Information Processing Letters
publication date: 2019-11-28T00:00:00Z
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 7138141
zbMATH Keywords: linear-time algorithm
zbMATH Keywords: chordal graphs
zbMATH Keywords: eccentricities
zbMATH Keywords: approximation
zbMATH Keywords: spanning trees
MaRDI profile type: Publication
full work available at URL: j.ipl.2019.105873
OpenAlex ID: W2981494155
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Q4729839
cites work: Fast approximation of centrality and distances in hyperbolic graphs
cites work: Diameter determination on restricted graph families
cites work: On the power of BFS to determine a graph's diameter
cites work: Eccentricity approximating trees
cites work: LexBFS-orderings and powers of chordal graphs
cites work: Easy computation of eccentricity approximating trees
cites work: Convexity in Graphs and Hypergraphs
cites work: Q3328583
cites work: Eccentricity-approximating trees in chordal graphs
cites work: Fast approximation algorithms for the diameter and radius of sparse graphs
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
DOI: 10.1016/J.IPL.2019.105873
description: scientific article; zbMATH DE number 7138141