Finding the <i>n</i> Most Vital Links in Flow Networks

The n most vital links of a flow network are defined as those n arcs whose simultaneous removal from the network causes the greatest decrease in the throughput capability of the remaining system between a specified pair of nodes. These n arcs are shown to be the n largest capacity arcs in a particular cut. A solution procedure is developed which involves sequentially modifying the network so as to make this cut eventually become the cut with smallest capacity. An algorithm with computational results is presented.

• 저널Management Science · 21(5) · 531–539
• 토픽VLSI and FPGA Design Techniques · Electrical and Electronic Engineering
• DOI10.1287/mnsc.21.5.531
• 저자H. Donald Ratliff, G. Thomas Sicilia, S. Lubore