Vikrant Ashvinkumar, Rutgers University

Abstract

Let G be an unweighted directed graph. You're permitted to add no more than a nearly linear number of extra “shortcut” edges to G, subject to their not violating the reachability relation already defined by G. How short are you able to make the longest shortest path between reachable pairs of vertices? What is this useful for? Let’s talk about it.

See: https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html