Combinatorics Seminar 2017

Speaker: Lalla Mouatadid, University of Toronto

Date: Fri, Dec 15, 2017

Time: 11:00 - 12:00

Venue: Middle Meeting Room

Title: Graph searches on structured families of graphs


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 families of graphs. Some families of graphs have a vertex ordering characterization, and we review how graph searching is used to produce such vertex orderings. These orderings 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 focus on two graph searches: Lexicographic breadth first search (LexBFS), and Lexicographic depth first search (LexDFS). In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. If time permits, we will discuss the relationship between graph searches and graph convexities.