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 searchbased 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:0015: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:0015:00
Information:

Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
