The k most vital arcs in the shortest path problem (Q1119183)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The k most vital arcs in the shortest path problem |
scientific article |
Statements
The k most vital arcs in the shortest path problem (English)
0 references
1989
0 references
The k most vital arcs in a network are those whose removal from the network results in the greatest increase in the shortest distance between two specified nodes. An exact algorithm is proposed to determine the k most vital arcs. Furthermore, an algorithm of time complexity equal to that of Dijkstra's algorithm for the shortest path problem is developed to solve the single most vital arc problem.
0 references
distance algorithm
0 references
most vital arcs
0 references
exact algorithm
0 references
Dijkstra's algorithm
0 references
shortest path
0 references
