Date : Feb. 17, 2022, 2 p.m. - Room :Amphi 2 - Pôle commun

On some algorithmic problems related to graph searches and beyond

Michel 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.