[theory-seminar] This week's theory seminar

[Bruce Spang]

Hi all,

This week’s theory seminar will feature Lalla Mouatadid talking about "Graph Searches on Structured Families of Graphs.” It will be on Wednesday, 10/16 from 3-4pm in Gates 463A.

The abstract is below. Hope to see you there!

Bruce

Graph Searches on Structured Families of Graphs
Lalla Mouatadid

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20191014/801686fd/attachment.html>