Cut Tree Algorithms:
An Experimental Study

Overview



The Cut Tree Problem:
Suppose that we are given a graph G(V, E), with |V| = m and |E| = m, and each edge e of the graph has a non-negative weight w(e). We want to find the max-flow/min-cut value of G for every pair of nodes s, t.
It can be shown [GH'61] that there are at most n-1 distinct min-cuts among the (n 2) total pairs of nodes. Moreover these n-1 min-cuts can be represented by a (not necessarily unique) tree, called Cut-Tree, which always exists and has the following properties:

  • The nodes of the tree are the same as the nodes of the initial graph, (i.e. V). Each edge is assigned a value (not directly related to the weights w(e) of the initial graph).
  • For every pair s, t, we can find the min-cut value by following the (unique) path between s and t in the cut-tree. Suppose that e is the edge with minimum value on that path. Then value(e) is also the min-cut value between s and t in the initial graph.
  • To actually find the cut between s and t, we simply cut off the edge e of minimum value on the s-t path. The two connected subsets of nodes in the tree, also define the min-cut between s and t in the initial graph.

    There are two main algorithms to find the Cut-Tree of a graph. If T(max-flow) is the time to perform one max-flow computation between two nodes in the initial graph, then both algorithms run in time O(n*T(max-flow)). These algorithms are:
  • Gomory-Hu's algorithm [GH'61], which is the first algorithm found for this problem and
  • Gusfield's algorithm [Gus'90], which implementation-wise is much simpler than the previous one. Here, we are studying the performance of these two algorithms on several input families of graphs. We also study heuristics to speed up the above algorithms.

    Absract:
    This is an experimental study of algorithms for the cut tree problem. We study the Gomory-Hu and Gusfield's algorithms as well as heuristics aimed to make the former algorithm faster. We develop an efficient implementation of the Gomory-Hu algorithm. We also develop problem families for testing cut tree algorithms. In our tests, the Gomory-Hu algorithm with a right combination of heuristics was significantly more robust than Gusfield's algorithm.





    Last Updated: Fri Nov 19 14:58:27 EST 1999
    Back to the main page.