In this talk, we will explore « graphs of shortest paths » which are directed acyclic graphs (DAGs) that appear using shortest path traversals of a graph from a fixed source. After establishing a precise definition of these structures, we will examine methods for uniformly sampling them and investigate their typical shape. Along the way, we will uncover interesting connections to bipartite graphs and graded posets.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne