The k most vital arcs in the shortest path problem (Q1119183): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0167-6377(89)90065-5 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W4245095675 / rank | |||
Normal rank | |||
Revision as of 18:22, 19 March 2024
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
