Seminars & Colloquia
University of Toronto
"Graph Searches on Structured Families of Graphs"
Wednesday August 22, 2018 10:30 AM
Location: 3211, EB2 NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
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.
Host: Blair Sullivan, CSC