Premium
On the power of BFS to determine a graph's diameter
Author(s) -
Corneil Derek G.,
Dragan Feodor F.,
Köhler Ekkehard
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10098
Subject(s) - combinatorics , lexicographical order , upper and lower bounds , graph , mathematics , constant (computer programming) , induced subgraph , discrete mathematics , algorithm , computer science , mathematical analysis , programming language , vertex (graph theory)
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 than k , BFS finds an estimate of the diameter that is no worse than diam( G ) − ⌊ k /2⌋. © 2003 Wiley Periodicals, Inc.