Flow equivalent trees in undirected node-edge-capacitated planar graphs
Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E -> R+, n = vertical bar V vertical bar, an s - t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s - t edge cut is an s - t edge cut with the minimum cut value among all s - t edge cuts. A theorem given by Gomory and Hu states that there are only n - 1 distinct values among the n(n - 1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation. (c) 2006 Elsevier B.V. All rights reserved.
flow equivalent tree node-edge-capacitated planar graphs minimum cut graph algorithms data structures