The power of Lexicographic Breadth First Search (LBFS)

Derek Corneil,
Department of Computer Science,
University of Toronto.

ABSTRACT

The concept of systematically searching a graph was first developed over a
century ago.  In the late 60s and 70s, considerable attention was given to
the algorithmic importance of the two most obvious search strategies,
namely Depth First Search and Breadth First Search.  In 1976 Rose, Tarjan
and Lueker developed a variation of Breadth First Search called
Lexicographic Breadth First Search (LBFS).  They showed that LBFS yields a
very simple linear time algorithm for recognizing chordal graphs (graphs
without induced cycles of size greater than 3).  Although a little work
was done on LBFS for the following 15 years, recently it has received a
great deal of attention. In particular it has been shown that LBFS can be
used both alone and in multiple sweeps to recognize various restricted
families of graphs as well as to determine specific properties on such
graphs.

In this talk we survey these results and indicate open problems in the
area.

*******************************************************