A parameter for vulnerability evaluation of packet switchedcommunication networks

摘要

The author provides certain properties of the minimum density of acut set and finds its relation to the connectivity vector. He alsoprovides an efficient algorithm which finds a tight upper bound to theminimum cut density and determines the location of a corresponding cutin the network. The proposed algorithm provides an efficient way toidentify a cut set the density of which is often the minimum one or atight upper bound to the minimum density. However, the minimum densityand the sparse cut itself can always be found from a linearprogram