at 14:00
Tel-Aviv University - Computer Science Colloquium
Sunday, December 12, 14:15-15:15
at 14:00
Room 309, Schreiber Building
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 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.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html