Approaches to the Minimum Cut Problem in a Class of Practical Networks
一类实际网络中的最小截算法

The minimum cut problem between two distinguished nodes in a undirected planar network with limited capacities on both nodes and edges is discussed. The traditional method reduces the node-edge-capacity problem to an only-edge-capacity problem. But this method does not maintain the planarity of a planar network, so the special qualities of planar networks can not be used. The traditional algorithm runs in time O(n2logn). In this paper, approaches that fully use the planarity of planar networks are presented. For an s-t network in which the source and the sink are on a same face, the minimum cut problem to the shortest path problem in a planar graph is reduced, thus an algorithm that runs in time O(n) is obtained. For a common planar network, another method that reduces the node-edge-capacity problem to an only-edge-capacity problem is presented. This reduction method does not destroy the planarity of a planar network, so that the problem can be solved in time O(nlogn).