H 2 New perspectives for graph searches on structured families of graphs

Auteurs : Habib, Michel (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
graph search generic search breadth first search lexicographic breadth first search lexicographic depth first search diameter computations cycles with LexBFS greedy aspects of LDFS

Résumé : 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 families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings 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) on some special classes of graphs such as cocomparability graphs.
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.

Codes MSC :
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science

Ressources complémentaires :

    Informations sur la Vidéo

    Langue : Français
    Date de publication : 22/03/2018
    Date de captation : 14/03/2018
    Collection : Research School ; Combinatorics ; Computer Science
    Format : MP4 (.mp4) - HD
    Durée : 01:01:27
    Domaine : Computer Science ; Combinatorics
    Audience : Chercheurs ; Doctorants , Post - Doctorants ; Etudiants Science Cycle 2
    Download : https://videos.cirm-math.fr/2018-03-14_Habib.mp4

Informations sur la rencontre

Nom de la rencontre : ALEA Days / Journées ALEA
Organisateurs de la rencontre : Busic, Ana ; Genitrini, Antoine ; Mairesse, Jean ; Martin, James
Dates : 12/03/2018 - 16/03/2018
Année de la rencontre : 2018
URL Congrès : https://conferences.cirm-math.fr/1776.html

Citation Data

DOI : 10.24350/CIRM.V.19374303
Cite this video as: Habib, Michel (2018). New perspectives for graph searches on structured families of graphs. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19374303
URI : http://dx.doi.org/10.24350/CIRM.V.19374303

Voir aussi


Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée