Show simple item record

The Complexity of Finding Most Vital Arcs and Nodes

dc.contributor.authorBar-Noy, Amotzen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorSchieber, Baruchen_US
dc.description.abstractLet $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.extent132437 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3539en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-96en_US
dc.titleThe Complexity of Finding Most Vital Arcs and Nodesen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record