The k most vital arcs in the shortest path problem
type: Item
instance of: scholarly article
title: The k most vital arcs in the shortest path problem
zbMATH Open document ID: 0669.90090
DOI: 10.1016/0167-6377(89)90065-5
author: S. H. Smith
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4097146
zbMATH Keywords: distance algorithm
zbMATH Keywords: most vital arcs
zbMATH Keywords: exact algorithm
zbMATH Keywords: Dijkstra's algorithm
zbMATH Keywords: shortest path
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90065-5
OpenAlex ID: W4245095675
cites work: Faster algorithms for the shortest path problem
cites work: Finding the most vital arcs in a network
cites work: Most vital links and nodes in weighted networks
cites work: Q3883524
cites work: Q5514188
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: A priority queue in which initialization and queue operations takeO(loglogD) time
cites work: An efficient algorithm for K shortest simple paths
cites work: Q4039868
description: scientific article; zbMATH DE number 4097146