网络最小覆盖流问题

The minimum cover flow problem in networks

网络流理论中最基本的模型是最大流及最小费用流问题.为研究堵塞现象,文献中出现了最小饱和流问题,但它是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.