一类实际网络中的最小截算法
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
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为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).

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2002-04-12
  • 最后修改日期:2002-09-11
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号