TY - JOUR

T1 - The minimum vulnerability problem on graphs

AU - Aoki, Yusuke

AU - Halld´Orsson, Bjarni V.

AU - Halld´Orsson, Magn´Us M.

AU - Ito, Takehiro

AU - Konrad, Christian

AU - Zhou, Xiao

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014

PY - 2014

Y1 - 2014

N2 - we pay cost(e), but cannot be shared by more than cap(e) paths even if we pay the cost of e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem remains NP-hard even for bipartite series-parallel graphs and for threshold graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number k of required paths.

AB - we pay cost(e), but cannot be shared by more than cap(e) paths even if we pay the cost of e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem remains NP-hard even for bipartite series-parallel graphs and for threshold graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number k of required paths.

UR - http://www.scopus.com/inward/record.url?scp=84921644939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921644939&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-12691-323

DO - 10.1007/978-3-319-12691-323

M3 - Article

AN - SCOPUS:84921644939

SN - 0302-9743

VL - 8881

SP - 131

EP - 299

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -