Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] This week's theory seminar

Bruce Spang bspang at stanford.edu
Mon Oct 14 10:06:16 PDT 2019


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>


More information about the theory-seminar mailing list