On the power of BFS to determine a graph's diameter
Authors:
- 23 September 2003
- Vol. 42 (4) , 209-222
Abstract
Recently, considerable effort has been spent on showing that Lexicographic Breadth First Search (LBFS) can be used to determine a tight bound on the diameter of graphs from various restricted classes. In this paper, we show that, in some cases, the full power of LBFS is not required and that other variations of Breadth First Search (BFS) suffice. The restricted graph classes that are amenable to this approach all have a small constant upper bound on the maximum‐sized cycle that may appear as an induced subgraph. We show that, on graphs that have no induced cycle of size greater thank, BFS finds an estimate of the diameter that is no worse than diam(G) − ⌊k/2⌋.Keywords
Funding Information
- Natural Science and Engineering Research Council of Canada
This publication has 11 references indexed in Scilit:
- On linear and circular structure of (claw, net)-free graphsDiscrete Applied Mathematics, 2003
- All pairs almost shortest paths2002
- Diameter determination on restricted graph familiesDiscrete Applied Mathematics, 2001
- Almost diameter of a house-hole-free graph in linear time via LexBFSDiscrete Applied Mathematics, 1999
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)SIAM Journal on Computing, 1999
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free GraphsSIAM Journal on Computing, 1999
- Matrix multiplication via arithmetic progressions1987
- Algorithmic Aspects of Vertex Elimination on GraphsSIAM Journal on Computing, 1976
- Minimax Location of a Facility in an Undirected Tree GraphTransportation Science, 1973
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962