# The Complexity of Finding Most Vital Arcs and Nodes

 dc.contributor.author Bar-Noy, Amotz en_US dc.contributor.author Khuller, Samir en_US dc.contributor.author Schieber, Baruch en_US dc.date.accessioned 2004-05-31T22:35:00Z dc.date.available 2004-05-31T22:35:00Z dc.date.created 1995-11 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/763 dc.description.abstract Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs (or nodes) are those $k$ arcs (nodes) whose removal maximizes the increase in the length of the shortest path from $s$ to $t$. We prove that finding the $k$ most vital arcs (or nodes) is NP-hard, even when all arcs have unit length. We also correct some errors in an earlier paper by Malik, Mittal and Gupta [ORL 8:223-227, 1989]. (Also cross-referenced as UMIACS-TR-95-96) en_US dc.format.extent 132437 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3539 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-95-96 en_US dc.title The Complexity of Finding Most Vital Arcs and Nodes en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿