Graph Searches, Cocomparability Graphs and Posets
Graphs, Hypergraphs, and Computing
23 January 15:30 - 16:30
Derek G. Corneil - University of Toronto
Graph searching is a fundamental tool in the design of efficient, easily implementable graph algorithms. Breadth First Search (BFS) and Depth First Search (DFS) were described in the late 19th century as strategies for maze traversal and since the 1970s have been shown to have applications in such areas as distance calculation, network flows, and planar graph recognition. In a seminal paper in 1976, Rose, Tarjan and Lueker presented Lexicographic BFS (LBFS) and showed that it could be used to produce a linear time algorithm for recognizing chordal graphs (every cycle of length greater than 3 has a chord). Somewhat surprisingly, few other applications of LBFS were discovered until the mid 1990s. Since then, many new applications of LBFS have appeared, often using LBFS is a multisweeping fashion. Recent applications of LBFS include forming the foundation for new, efficient algorithms for both modular and split decomposition - two fundamental graph operations.
The success of LBFS raised the question of whether there is a similar Lexicographic version of DFS. Such a search was discovered almost 10 years ago, but only recently has it been shown to have applications, in particular to Partially Ordered Sets (posets) as well as to cocomparability graphs (graphs whose complement has a transitive orientation of its edges).
In this talk we survey these topics and present vertex ordering characterizations of various graph searching algorithms. The talk concludes with open questions.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU