| 本文已被：浏览 4463次 下载 5770次 |
码上扫一扫！ |
|
|
| 一类实际网络中的最小截算法 |
|
张宪超1,2, 万颖瑜1,2, 陈国良1,2
|
|
1.中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;2.国家高性能计算中心,合肥,安徽,合肥,230027
|
|
| 摘要: |
| 讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决. |
| 关键词: 组合优化 网络优化 最大流 最小截 平面图 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032700 (国家重点基础研究发展规划(973)) |
|
| Approaches to the Minimum Cut Problem in a Class of Practical Networks |
|
ZHANG Xian-Chao,WAN Ying-Yu,CHEN Guo-Liang
|
| 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). |
| Key words: combinatorial optimization network optimization maximum flow minimum cut planar graph |
