Finding the most vital arcs in a network
The most vital arc problem in a directed, double arc weighted network is considered. It consists in finding a feasible subset of arcs whose removal leads to the greatest increase in the shortest path length between two specified nodes. The problem is shown to be NP-hard, and a polynomial time algorithm providing a lower bound on the optimal solution value is presented.
scientific article; zbMATH DE number 4114419