The Complexity of Computing Path Length Distributions with Edges i.i.d. Random via Local Uniformity

Ei Ando

We investigate the problem of computing the distribution function for the shortest and longest path lengths in a directed graph with random edge lengths. Specifically, when these l…