Français
New perspectives for graph searches on structured families of graphs
Post-edited
Authors : Habib, Michel (Author of the conference)
CIRM (Publisher )
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science
Additional resources :
https://www.cirm-math.fr/ProgWeebly/Renc1776/Habib.pdf
CIRM (Publisher )
Abstract :
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.
MSC Codes : 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
Additional resources :
https://www.cirm-math.fr/ProgWeebly/Renc1776/Habib.pdf
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : French Available date : 22/03/2018 Conference Date : 14/03/2018 Subseries : Research School arXiv category : Computer Science ; Combinatorics Mathematical Area(s) : Computer Science ; Combinatorics Format : MP4 (.mp4) - HD Video Time : 01:01:27 Targeted Audience : Researchers ; Graduate Students Download : https://videos.cirm-math.fr/2018-03-14_Habib.mp4 
|
Information on the Event
Event Title : ALEA Days / Journées ALEAEvent Organizers : Busic, Ana ; Genitrini, Antoine ; Mairesse, Jean ; Martin, James Dates : 12/03/2018 - 16/03/2018 Event Year : 2018 Event URL : https://conferences.cirm-math.fr/1776.html
Citation Data
DOI : 10.24350/CIRM.V.19374303Cite 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 |
See Also
- [Multi angle] Comptage et design multiple d'ARN / Author of the conference Ponty, Yann.
- [Multi angle] Sur les mesures stationnaires des VLMC / Author of the conference Pouyanne, Nicolas.
- [Multi angle] Chemins à grands pas dans le quadrant / Author of the conference Bousquet-Mélou, Mireille.
Bibliography
