First Lecture
Title: Graph Searches I

Abstract: In this work we will study a graph search (also called graph traversal) as an operator acting on a graph and producing a total order of the vertices (namely the visiting ordering of the graph search). We first recall the characterizations obtained by Corneil and Krueger (2008) of the visiting orderings of the main classical graph searches: Breadth First Search (BFS), Depth First Search (DFS), and their lexicographic variations (LBFS and LDFS). We will show how these characterizations can be used to find very elegant proofs of search-based graph algorithms. We will finish by an ongoing application of BFS to compute efficiently the diameter of huge graphs.

Time and Date: Sunday, May 14, 2017, 14:00-15:00

Second Lecture
Title: Graph Searches II

Abstract: We will introduce a new formalism in order to show that graph search is just playing with vertex orderings, introducing multisweep algorithms. A multisweep algorithm is just made up with a series of consecutive graph searches, including a $+$ rule from one search to the following. We will present how this rule has been successfully used with LBFS for the recognition of many graph classes (proper interval graphs, interval graphs ...) and extend it to the recognition of cocomparability graphs (a cocomparability graph is a graph whose complement admits a transitive orientation). We finish by presenting two new graph lexicographic searches LexUP and LexDown that could be useful for some applications. .

Time and Date: Monday, May 15, 2017, 14:00-15:00





Information: