Abstract: Graph searching — a mechanism to traverse a graph visiting one vertex at a time in a specific manner — is a powerful tool used to extract structure from various graph classes. Some of these graph classes have characterizing vertex orderings, which expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance).

 

In this talk, we illustrate how to use graph searching to 1. extract these orderings and 2. exploit the structure algorithmically. We focus on two graph searches: Lexicographic breadth first search (LexBFS), and Lexicographic depth first search (LexDFS); and in particular, on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs, and prove fixed point type theorems for LexBFS. If time permits, we will discuss the relationship between graph searches and convex geometries.

Short Bio: Lalla Mouatadid is a Ph.D student in the Theory Group at the Department of Computer Science at the University of Toronto, working under the supervision of Derek Corneil and Allan Borodin. Her research interests lie in graph theory and algorithms, including both the use of searches to design linear time algorithms for structured families of graphs and the generation of combinatorial objects.