TY - JOUR

T1 - Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

N1 - Funding Information:
This research was supported by the National Science Foundation (Grant IIS-0118635). The authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science. A short conference version of this paper, titled “Generating Paths and Cuts in Multi-Pole (Di)Graphs,” appeared in the Proceedings of the 29th International Symposium on the Mathematical Foundations of Computer Science, MFCS 2004 (J. Fiala, V. Koubek, J. Kratochvíl (Eds.), Prague, Czech Republic, August 22–27, 2004), Lecture Notes in Computer Science, vol. 3153, Springer, Berlin, Heidelberg, New York, 2004, pp. 298–309.

PY - 2007/1/15

Y1 - 2007/1/15

N2 - Let G = (V, E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s1 and s2 to, respectively, a given vertex t1, and each vertex of a given subset of vertices T2.

AB - Let G = (V, E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s1 and s2 to, respectively, a given vertex t1, and each vertex of a given subset of vertices T2.

KW - Disjunction and conjunctions of paths and cuts

KW - Path and cut enumeration

KW - Reliability theory

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

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

U2 - 10.1016/j.dam.2006.04.032

DO - 10.1016/j.dam.2006.04.032

M3 - Article

AN - SCOPUS:33751167402

SN - 0166-218X

VL - 155

SP - 137

EP - 149

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -