OrderedCuts: A new approach for computing Gomory-Hu tree
share
The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum s-t cuts of an undirected weighted graph for all pairs of nodes (s,t). We propose a new approach for computing the cut tree based on a reduction to the problem that we call OrderedCuts. Given a sequence of nodes s,v_1,…,v_ℓ, its goal is to compute minimum {s,v_1,…,v_i-1}-v_i cuts for all i∈[ℓ]. We show that the cut tree can be computed by Õ(1) calls to OrderedCuts. We also establish new results for OrderedCuts that may be of independent interest. First, we prove that all ℓ cuts can be stored compactly with O(n) space in a data structure that we call an OC tree. We define a weaker version of this structure that we call depth-1 OC tree, and show that it is sufficient for constructing the cut tree. Second, we prove results that allow divide-and-conquer algorithms for computing OC tree. We argue that the existence of divide-and-conquer algorithms makes our new approach a good candidate for a practical implementation.
READ FULL TEXT