List all vertex sets that are minimal (s,t) separators for
some s and t, in an undirected graph.
Usage
minimal.st.separators(graph)
Arguments
graph
The input graph. It may be directed, but edge directions
are ignored.
Value
A list of numeric vectors. Each vector contains a vertex set (defined
by vertex ids), each vector is an (s,t) separator of the input graph,
for some $s$ and $t$.
concept
Minimal (s,t) separators
Vertex separator
Details
A $(s,t)$ vertex separator is a set of vertices, such that after
their removal from the graph, there is no path between $s$ and
$t$ in the graph.
A $(s,t)$ vertex separator is minimal if none of its subsets is an
$(s,t)$ vertex separator.
References
Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All the
Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer
and Stephan Eidenbenz (editors): Graph-theoretic concepts in
computer science, 1665, 167--172, 1999. Springer.