###
DOI:
Journal of Software:2003.14(5):885-890

一类实际网络中的最小截算法
张宪超,万颖瑜,陈国良
(中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;国家高性能计算中心,合肥,安徽,合肥,230027)
Approaches to the Minimum Cut Problem in a Class of Practical Networks
ZHANG Xian-Chao,WAN Ying-Yu,CHEN Guo-Liang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2803   Download 2587
Received:April 12, 2002    Revised:September 11, 2002
> 中文摘要: 讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.
中文关键词: 组合优化  网络优化  最大流  最小截  平面图
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 does not destroy the planarity of a planar network, so that the problem can be solved in time O(nlogn).
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032700 (国家重点基础研究发展规划(973)) Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032700 (国家重点基础研究发展规划(973))
Foundation items:
Reference text:

张宪超,万颖瑜,陈国良.一类实际网络中的最小截算法.软件学报,2003,14(5):885-890

ZHANG Xian-Chao,WAN Ying-Yu,CHEN Guo-Liang.Approaches to the Minimum Cut Problem in a Class of Practical Networks.Journal of Software,2003,14(5):885-890