Graphs of Shortest Paths
Naima Mehdi (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.