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

by: Derek G Corneil, Feodor F Dragan, Ekkehard Köhler

Networks, Vol. 42, No. 4. (2003), pp. 209-222.

View FullText article

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, graph

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 than k, BFS finds an estimate of the diameter that is no worse than diam(G) - ?k/2?. © 2003 Wiley Periodicals, Inc.

@article{citeulike:2169751, 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 than k, BFS finds an estimate of the diameter that is no worse than diam(G) - ?k/2?. {\copyright} 2003 Wiley Periodicals, Inc.}, address = {Department of Computer Science, University of Toronto, Toronto, Ontario, Canada; Department of Computer Science, Kent State University, Kent, Ohio; Institut f\"{u}r Mathematik, Technische Universit\"{a}t Berlin, Berlin, Germany}, author = {Corneil, Derek G. and Dragan, Feodor F. and K\"{o}hler, Ekkehard }, citeulike-article-id = {2169751}, doi = {http://dx.doi.org/10.1002/net.10098}, journal = {Networks}, keywords = {algorithms, graph}, number = {4}, pages = {209--222}, posted-at = {2007-12-26 10:42:06}, priority = {2}, title = {On the power of BFS to determine a graph's diameter}, url = {http://dx.doi.org/10.1002/net.10098}, volume = {42}, year = {2003} }

RIS record

TY - JOUR ID - citeulike:2169751 L3 - citeulike-article-id:2169751 TI - On the power of BFS to determine a graph's diameter JF - Networks VL - 42 IS - 4 SP - 209 EP - 222 AD - Department of Computer Science, University of Toronto, Toronto, Ontario, Canada; Department of Computer Science, Kent State University, Kent, Ohio; Institut für Mathematik, Technische Universität Berlin, Berlin, Germany N2 - 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. KW - algorithms KW - graph AU - Corneil, Derek AU - Dragan, Feodor AU - Köhler, Ekkehard PY - 2003/// UR - http://dx.doi.org/10.1002/net.10098 ER -

RIS BibTeX