Séminaire Algorithmique : « Graphs of Shortest Paths », Mehdi Naima (LIP6, Sorbonne Univ.)

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.