On the power of BFS to determine a graph's diameter

DOI10.1002/net.10098zbMath1036.68072OpenAlexW2082613046MaRDI QIDQ4446912

Feodor F. Dragan, Ekkehard Köhler, Derek Gordon Corneil

Publication date: 3 February 2004

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10098

zbMATH Keywords

AT-free graphsbreadth first searchlinear-time algorithm\(k\)-chordal graphsgraph diameter approximation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (11)

How to use spanning trees to navigate in graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem ⋮ A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs ⋮ Incremental Map Generation (IMG) ⋮ An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Computing Giant Graph Diameters ⋮ Linear-time graph distance and diameter approximation ⋮ Fellow travelers phenomenon present in real-world networks ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

Cites Work

• Almost diameter of a house-hole-free graph in linear time via LexBFS
• On linear and circular structure of (claw, net)-free graphs
• Representation of a finite graph by a set of intervals on the real line
• Algorithmic Aspects of Vertex Elimination on Graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• All-Pairs Almost Shortest Paths
• Diameter determination on restricted graph families

This page was built for publication: On the power of BFS to determine a graph's diameter