# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Generating Paths and Cuts in Multi-pole (Di)graphs

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., & Makino, K. (2004). Generating
Paths and Cuts in Multi-pole (Di)graphs. In *Mathematical foundations of computer science 2004: 29th
International Symposium, MFCS 2004* (pp. 298-309). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2922-5

##### Abstract

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given
a set 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 . For undirected graphs, we show that the enumeration
problems for conjunctions of paths and disjunctions of cuts can be solved in
incremental polynomial time. For directed graphs both of these problems are
NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets
of arcs connecting respectively two given nodes s1 and s2 to a given vertex t1,
and each vertex of a given subset of vertices T2.