An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs (2007)
Bhalgat, Anand, Hariharan, Ramesh, Kavitha, Telikepalli, Panigrahi, Debmalya
We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical...