Pruning based Distance Sketches with Provable Guarantees on Random Graphs

Hongyang Zhang, Huacheng Yu, Ashish Goel

Measuring the distances between vertices on graphs is one of the most fundamental components in network analysis. Since finding shortest paths requires traversing the graph, it is…