An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time

DOI10.1016/j.ipl.2019.105873zbMath1481.05029OpenAlexW2981494155MaRDI QIDQ2011037

Feodor F. Dragan

Publication date: 28 November 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2019.105873

zbMATH Keywords

approximationchordal graphsspanning treeslinear-time algorithmeccentricities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Helly-gap of a graph and vertex eccentricities ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Eccentricity function in distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• LexBFS-orderings and powers of chordal graphs
• Eccentricity-approximating trees in chordal graphs
• Easy computation of eccentricity approximating trees
• Fast approximation of centrality and distances in hyperbolic graphs
• Eccentricity approximating trees
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Convexity in Graphs and Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• On the power of BFS to determine a graph's diameter
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Diameter determination on restricted graph families

This page was built for publication: An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time