Naima Mehdi (LIP6, Sorbonne Univ.)

‐ 10:45

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.