A computational study of Gomory-Hu tree algorithms

We present an experimental study of algorithms for computing the Gomory-Hu tree (aka cut tree) in undirected weighted graphs. We develop a new implementation based on two popular maxflow algorithms, IBFS and BK. We compare it with the algorithms from the previous experimental study by Goldberg and Tsioutsiouliklis (2001) and with the more recent algorithm by Akibo et al. (2016) (designed for unweighted simple graphs). Results indicate that on some classes of problems new implementation significantly outperforms previous methods. We also formulate a version of the Gomory-Hu algorithm tree for computing a \emph{partial} tree, and establish a new bound on its complexity.