Finding the most vital arcs in a network
type: Item
instance of: scholarly article
title: Finding the most vital arcs in a network
zbMATH Open document ID: 0679.90086
DOI: 10.1016/0167-6377(89)90003-5
author: Michael O. Ball
author: Rakesh V. Vohra
author: Bruce Golden
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
reviewed by: Jerzy Kamburowski
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4114419
zbMATH Keywords: most vital arc
zbMATH Keywords: directed, double arc weighted network
zbMATH Keywords: shortest path
zbMATH Keywords: NP- hard
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: lower bound
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90003-5
OpenAlex ID: W1999293689
cites work: Most vital links and nodes in weighted networks
cites work: Maximizing the minimum source-sink path subject to a budget constraint
cites work: Q4198056
cites work: A problem in network interdiction
cites work: The complexity of finding maximum disjoint paths with length constraints
cites work: The k most vital arcs in the shortest path problem
cites work: An \(O(IVI^3)\) algorithm for finding maximum flows in networks
cites work: Exact cuts in networks
description: scientific article; zbMATH DE number 4114419