Finding the most vital arcs in a network (Q1823164)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding the most vital arcs in a network |
scientific article |
Statements
Finding the most vital arcs in a network (English)
0 references
1989
0 references
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.
0 references
most vital arc
0 references
directed, double arc weighted network
0 references
shortest path
0 references
NP- hard
0 references
polynomial time algorithm
0 references
lower bound
0 references
