English
New perspectives for graph searches on structured families of graphs
Post-edited
Auteurs : Habib, Michel (Auteur de la conférence)
CIRM (Editeur )
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science
Ressources complémentaires :
https://www.cirm-math.fr/ProgWeebly/Renc1776/Habib.pdf
CIRM (Editeur )
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 : 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.
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science
Ressources complémentaires :
https://www.cirm-math.fr/ProgWeebly/Renc1776/Habib.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Français Date de Publication : 22/03/2018 Date de Captation : 14/03/2018 Sous Collection : Research School Catégorie arXiv : Computer Science ; Combinatorics Domaine(s) : Informatique ; Combinatoires Format : MP4 (.mp4) - HD Durée : 01:01:27 Audience : Chercheurs ; 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 ALEAOrganisateurs 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 de la Rencontre : https://conferences.cirm-math.fr/1776.html
Données de citation
DOI : 10.24350/CIRM.V.19374303Citer cette vidéo: 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
- [Multi angle] Comptage et design multiple d'ARN / Auteur de la conférence Ponty, Yann.
- [Multi angle] Sur les mesures stationnaires des VLMC / Auteur de la conférence Pouyanne, Nicolas.
- [Multi angle] Chemins à grands pas dans le quadrant / Auteur de la conférence Bousquet-Mélou, Mireille.
Bibliographie
