Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs
verfasst von : L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
=(
V
,
E
) be an undirected graph, and let
B
⊆
V
×
V
be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets
X
⊆
E
such that every vertex pair (
s
,
t
) ∈
B
is disconnected in
$(V,E \smallsetminus X)$
, generalizing well-known efficient algorithms for enumerating all minimal
s
-
t
cuts, for a given pair
s
,
t
∈
V
of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets
X
⊆
E
such that no (
s
,
t
) ∈
B
is a bridge in (
V
,
X
∪
B
). These two enumeration problems are special cases of the more general cut conjunction problem in matroids: given a matroid
M
on ground set
S
=
E
∪
B
, enumerate all minimal subsets
X
⊆
E
such that no element
b
∈
B
is spanned by
$E \smallsetminus X$
. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (
V
,
E
∪
B
), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.