摘要
网络流理论中最基本的模型是最大流及最小费用流问题.为研究堵塞现象,文献中出现了最小饱和流问题,但它是NP-难的.研究类似的最小覆盖流问题,即求一流,使每一条弧的流量达到一定的额定量,而流的值为最小.主要结果是给出多项式时间算法,并应用于最小饱和流问题.
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.
出处
《运筹学学报》
CSCD
北大核心
2014年第4期96-104,共9页
Operations Research Transactions
基金
国家自然科学基金(Nos.11101383
61373106)
河南省教育厅自然科学基金(No.2010B110006)
关键词
网络流
最小覆盖流
多项式时间算法
network flow, minimum cover flow, polynomial-time algorithm