计算机应用 ›› 2013, Vol. 33 ›› Issue (07): 1805-1808.DOI: 10.11772/j.issn.1001-9081.2013.07.1805

• 网络与通信 • 上一篇    下一篇

连续时间容量网络的最短动态时间流问题

马宇斌,谢政,陈挚   

  1. 国防科学技术大学 理学院,长沙 410073
  • 收稿日期:2013-01-22 修回日期:2013-02-25 出版日期:2013-07-01 发布日期:2013-07-06
  • 通讯作者: 马宇斌
  • 作者简介:马宇斌(1988-),男,广东台山人,硕士研究生,主要研究方向:网络最优化;谢政(1960-),男,湖南衡阳人,教授,主要研究方向:网络最优化;陈挚(1965-),男,湖南湘乡人,副教授,主要研究方向:网络最优化。

Shortest dynamic time flow problem in continuous-time capacitated network

MA Yubin,XIE Zheng,CHEN Zhi   

  1. College of Science, National University of Defense Technology, Changsha Hunan 410073, China
  • Received:2013-01-22 Revised:2013-02-25 Online:2013-07-06 Published:2013-07-01
  • Contact: MA Yubin

摘要: 针对一类带节点处理速率限制的连续时间容量网络,提出了该网络中的最短动态时间流问题,并给出其线性规划形式;通过分析该网络与经典网络之间的内在联系,利用最大接收流和退流的思想分别设计出准确求解两种网络最短动态时间流的高效算法;证明了算法的正确性并分析出算法有较小的复杂度;最后,通过一个算例演示了算法的执行。

关键词: 连续时间容量网络, 节点处理速率, 最短动态时间流, 复杂度

Abstract: Concerning a kind of continuous-time capacitated network with limits on nodes process rate, a shortest dynamic time flow was proposed and its corresponding linear programming form was also given. Based on the inner relationship of the above-mentioned network and the classical continuous-time capacitated network, efficient algorithms in terms of the thought of maximal-received flow and returning flow were designed to precisely solve the shortest dynamic time flow issue in those two kinds of network respectively. Afterwards, the algorithms were proved to be correct and their complexities were also concluded to be small. Finally, an example was used to demonstrate the execution of the algorithm.

Key words: continuous-time capacitated network, node processing rate, shortest dynamic time flow, complexity

中图分类号: