【摘要】 考虑一种网络系统中的容量扩张问题 :给定网络N(V ,E , C) ,如何对容量向量 C进行扩张 ,在假设的每条边的扩张费用 (包括固定费用与成本费用 )的条件下 ,使得网络中最大容量树的容量尽可能提高 ,同时总的扩张费用不超过给定的预算D .讨论了此类问题的特性 ,并给出了解决问题的一个强多项式算法 .更多还原

【Abstract】 A type of capacity expansion problem on networks is considered. A network N (V, E , ) is given and the capacity vector is increased so that the capacity of the maximum capacity tree can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget limit, assuming that the cost of increment of capacity on each edge of network includes both fixed cost and increasing cost. A strong polynomial algorithm is proposed to solve the problem.更多还原