Use this if you are using igraph from R
min_st_separators {igraph} | R Documentation |
List all vertex sets that are minimal (s,t) separators for some s and t, in an undirected graph.
min_st_separators(graph)
graph |
The input graph. It may be directed, but edge directions are ignored. |
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.
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
.
Gabor Csardi csardi.gabor@gmail.com
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.
ring <- make_ring(4)
min_st_separators(ring)
chvatal <- make_graph("chvatal")
min_st_separators(chvatal)