In this talk, we will explore graphs of shortest paths — directed acyclic graphs (DAGs) derived from shortest path traversals of a graph rooted at 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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne