Determining the most vital link in a flow network

✍ Scribed by S. H. Lubore; H. D. Ratliff; G. T. Sicilia

• Publisher: John Wiley and Sons
• Year: 1971
• Tongue: English
• Weight: 356 KB
• Volume: 18
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/nav.3800180408

✦ Synopsis

The most vital link in a single commodity flow network is that arc whose removal results in the greatest reduction in the value of the maximal flow in the network between a source node and a sink node. This paper develops an iterative labeling algorithm to determine the most vital link in the network. A necessary condition for an arc to be the most vital link is established and is employed to decrease the number of arcs which must be considered.