Séminaire
|
Date : 17 février 2022 14:00 - Salle :Amphi 2 - Pôle commun
On some algorithmic problems related to graph searches and beyondMichel HABIB, Professeur émerite - IRIF |
This is joint work with many researchers including: Derek Corneil, Maxime Dupuy, Jérémie Dusart, Laurent Feuilloley, Lalla Mouatadib, Laurent Viennot.
Résumé: I will quickly sketch a panorama of the applications of standard graph searches such as Breadth First Search (BFS), Depth First Search (DFS) and their lexicographic variants. Then I will present their greedy aspects and their relation to convex geometries. I will introduce some nice (but hard) conjectures about multisweep algorithms which are used to capture the structure of a given graph.
These graph searches have many relationships with the recognition of well-structured graph classes. In particular graph classes that can be characterized by the existence of an ordering of the vertices avoiding some pattern (as for example a simplicial elimination ordering for chordal graphs). I will present our recent results in this direction.
To finish the presentation I will present the weather routing problem for boats, which can be seen as a graph search over an infinite graph, and I will discuss the difficulty of discretization and to have an algorithmic approach on this problem.