English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 96-104.

• 运筹学 • 上一篇    下一篇

网络最小覆盖流问题

林浩1,*, 林澜2     

  1. 1. 河南工业大学理学院, 郑州 450001;  2. 同济大学电子与信息工程学院, 上海 200092
  • 收稿日期:2014-03-04 出版日期:2014-12-15 发布日期:2014-12-15
  • 通讯作者: 林浩 E-mail:linhao@haut.edu.cn
  • 基金资助:

    国家自然科学基金(Nos. 11101383, 61373106), 河南省教育厅自然科学基金(No. 2010B110006)

The minimum cover flow problem in networks

LIN Hao1,*, LIN Lan2   

  1. 1. School of Science, Henan University of Technology, Zhengzhou 450001, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 200092, China
  • Received:2014-03-04 Online:2014-12-15 Published:2014-12-15

PDF

611

摘要： 网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.

关键词: 网络流, 最小覆盖流, 多项式时间算法

Abstract: The maximum flow problem and the minimum cost flow problem are two basic models in theory of network flows. In order to study the blocking phenomena, the minimum saturated flow problem has arisen in the literature, but it is NP-hard. This paper studies the minimum cover flow problem, that is, we look for a flow with minimum value such that the flow in each arc is not less than a prescribed amount. The main result is to establish a polynomial-time algorithm which can be applied to the minimum saturated flow problem.

Key words: network flow, minimum cover flow, polynomial-time algorithm

中图分类号: