TY - JOUR

T1 - Flow equivalent trees in undirected node-edge-capacitated planar graphs

AU - Zhang, Xianchao

AU - Liang, Weifa

AU - Jiang, He

PY - 2006/11/15

Y1 - 2006/11/15

N2 - Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E {mapping} R+, n = | V |, 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.

AB - Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E {mapping} R+, n = | V |, 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.

KW - Data structures

KW - Flow equivalent tree

KW - Graph algorithms

KW - Minimum cut

KW - Node-edge-capacitated

KW - Planar graphs

UR - http://www.scopus.com/inward/record.url?scp=33747098186&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.06.001

DO - 10.1016/j.ipl.2006.06.001

M3 - Article

SN - 0020-0190

VL - 100

SP - 110

EP - 115

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -