%0 Journal Article
%T Approaches to the Minimum Cut Problem in a Class of Practical Networks<br>一类实际网络中的最小截算法
%A ZHANG Xian-Chao
%A WAN Ying-Yu
%A CHEN Guo-Liang
%A <br>张宪超
%A 万颖瑜
%A 陈国良
%J 软件学报
%D 2003
%I 
%X 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).
%K combinatorial optimization
%K network optimization
%K maximum flow
%K minimum cut
%K planar graph<br>组合优化
%K 网络优化
%K 最大流
%K 最小截
%K 平面图
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=39AA84E7A71E5992&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=94C357A881DFC066&sid=745C7FAEA69986C7&eid=38DB5AF4AD8FDCCA&journal_id=1000-9825&journal_name=软件学报&referenced_num=9&reference_num=19