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

DOI10.1016/J.IPL.2019.105873MaRDI QIDQ2011037zbMATH OpenOpenAlexFDO

Authors 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

spanning treesapproximationchordal graphslinear-time algorithmeccentricities

Mathematics Subject Classification ID

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

Recommendations

• Eccentricity-approximating trees in chordal graphs
• Easy computation of eccentricity approximating trees
• Eccentricity approximating trees
• Eccentricity approximating trees (extended abstract)
• Distance approximating trees for chordal and dually chordal graphs (extended abstract)

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4114700 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Convexity in Graphs and Hypergraphs
• Diameter determination on restricted graph families
• Easy computation of eccentricity approximating trees
• Eccentricity approximating trees
• Eccentricity-approximating trees in chordal graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast approximation of centrality and distances in hyperbolic graphs
• LexBFS-orderings and powers of chordal graphs
• On the power of BFS to determine a graph's diameter
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

Cited in

(9)

• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Eccentricity approximating trees
• Easy computation of eccentricity approximating trees
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• A story of diameter, radius, and (almost) Helly property
• Eccentricity approximating trees (extended abstract)
• Helly-gap of a graph and vertex eccentricities
• Eccentricity function in distance-hereditary graphs
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities

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

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