Graph searches on structured families of graphs

Thursday, November 16, 2017 -
3:00pm to 4:00pm
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.
Lalla Mouatadid
University of Toronto
Event Location: 
Fine Hall 224