网络流改进边问题

Reformed arc network problems

基于网络流提出了网络流改进边问题,该问题考虑在给定网络图以及改进总费用的前提下,如何通过选择部分边扩充其容量达到网络流量最大的目的。通过构造背包问题到该问题的多项式变换,该问题被证明是NP-难解问题,为了更清楚描述该问题的计算复杂度,构造了顶点覆盖问题到该问题的多项式变换,进而证明该问题是强NP-难问题。最后提出了解决此问题的一个启发式算法并做了若干实验结果。

This paper proposes a problem based on network flow problems. It considers how to maximize flow from the source to the sink in the given graph by reforming some arcs within budget constraints to expand their capacities. By transformed from the knapsack problem and the vertex cover problem,this problem is proved to be NP-complete even when reforming one arc requires exactly one unit of resource. Moreover,a heuristic algorithm is proposed and some numerical results is listed finally.