一类实际网络中的最小截算法-CiteSeerX.PDF

1000-9825/2003/14(05)0885 ©2003 Journal of Software 软 件 学 报 Vol.14, No.5 ∗ 一类实际网络中的最小截算法 + 张宪超 , 万颖瑜, 陈国良 ( 中国科学技术大学 计算机科学与技术系,安徽 合肥 230027) ( 国家高性能计算中心(合肥),安徽 合肥 230027) Approaches to the Minimum Cut Problem in a Class of Practical Networks + ZHANG Xian-Chao , WAN Ying-Yu, CHEN Guo-Liang (Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) (National High Performance Computing Center at Hefei, Hefei 230027, China) + Corresponding author: E-mail: xczhang081@ Received 2002-04-12; Accepted 2002-09-11 Zhang XC, Wan YY, Chen GL. Approaches to the minimum cut problem in a class of practical networks. Journal of Software, 2003,14(5):885~890. /1000-9825/14/885.htm Abstract: 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 do