| 网络最小覆盖流问题 |
| |
| 引用本文： | 林浩,林澜.网络最小覆盖流问题[J].运筹学学报,2014,18(4):96-104. |
| |
| 作者姓名： | 林浩 林澜 |
| |
| 作者单位： | 1. 河南工业大学理学院, 郑州 450001; 2. 同济大学电子与信息工程学院, 上海 200092 |
| |
| 基金项目： | 国家自然科学基金(Nos.11101383,61373106);河南省教育厅自然科学基金(No.2010B110006) |
| |
| 摘 要： | 网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.
|
| 关 键 词： | 网络流 最小覆盖流 多项式时间算法 |
| 收稿时间： | 2014-03-04 |
The minimum cover flow problem in networks |
| |
| LIN Hao,LIN Lan.The minimum cover flow problem in networks[J].OR Transactions,2014,18(4):96-104. |
| |
| Authors: | LIN Hao LIN Lan |
| |
| Institution: | 1. School of Science, Henan University of Technology, Zhengzhou 450001, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 200092, China |
| |
| 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. |
| |
| Keywords: | network flow minimum cover flow polynomial-time algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
