An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, Anand Bhalgat · 2007
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 Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).