一类实际网络中的最小截算法

• 作者: 万颖瑜 张宪超 陈国良
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 组合优化 网络优化 最大流 最小截 平面图
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 885-890
• 页数: 6页
• 分类号: TP301
• 字数: 4057字
• 语种: 中文

摘要

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.