The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The comp...The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset arcs group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks.展开更多
基金supported by the Natural Science Foundation(Grant No.2001ABB013)the Key Science and Technology Foundation of Hubei Province(Grant No.2001AA104A05)
文摘The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset arcs group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks.
