Graph Searches Revisited A lego of graph searches

Michel Habib

Description

Niveau: Supérieur
Graph Searches Revisited : A lego of graph searches Graph Searches Revisited : A lego of graph searches Michel Habib Pretty Structures 2011, IHP, may 2011

• tie-break rules


• comparability graphs


• basic graph


• characterization using


• graph searches


• schedule generic


• lexicographic depth

Informations

• Publié par: chaeh
• Nombre de lectures: 10
• Langue: English

Extrait

Graph Searches Revisited : A lego of graph searches

Graph Searches Revisited : A lego of graph searches

Michel Habib [e-mail] http://www.liafa.jussieu.fr/ ~ habib

Pretty Structures 2011, IHP, may 2011

Graph Searches Revisited :

A lego of graph searches

Schedule Generic Search

Breadth First Search Depth First Search Lexicographic Breadth First Search LexBFS Lexicographic Depth First Search LexDFS

Maximal Neighbourhood Search (MNS) Lego with basic graph searches Importance of 4 points conditions for graph recognition The set of all simplicial schemes Principle of a Composition of Searches Hamiltonicity on co-comparability graphs

Graph Searches Revisited :

A lego of graph searches

Graph searches are very well known and used

1.

2.

3.

Euler (1735) for solving the famous walk problem in Kœnisberg Tremeaux (1882) and Tarry (1895) using DFS to solve maze problems Computer scientists from 1950 ....

Graph Searches Revisited :

A lego of graph searches

Two main aspects for a

1.

2.

graph search :

its principle or its algorithm (i.e. the description of the tie-break rules for the choice of the next vertex (edge) to be explored ) its implementation or its program

Graph Searches Revisited :

A lego of graph searches

We will focus here on a third one : I its characterization using forbidden structures and the relationships with the algorithm I try to convince you that these characterizations can beI will helpful

Graph Searches Revisited :

A lego of graph searches

Problem For an undirected graphG= (V,E), explore the vertices ofG”traversing or following” the edges.

Result I a tree structure rooted at the first visited vertex I an orderingσof the vertices

Questions I Under which conditions an orderingσof the vertices corresponds to a search ? I  ?What are the properties of these orderings

Graph Searches Revisited :

A lego of graph searches

Main reference for this today lecture :

These easy questions have been only recently systematically considered : D.G. Corneil et R. M. Krueger, A unified view of graph searching, SIAM J. Discrete Math, 22, N˚4 (2008) 1259-1276

Graph Searches Revisited : Generic Search

A lego of graph searches

Generic Search

Breadth First Search

Depth First Search

Lexicographic Breadth First Search LexBFS

Lexicographic Depth First Search LexDFS

Maximal Neighbourhood Search (MNS)

Lego with basic graph searches

Importance of 4 points conditions for graph recognition

The set of all simplicial schemes

Principle of a Composition of Searches

Hamiltonicity on co-comparability graphs