List all vertex sets that are minimal (s,t) separators for some s and t, in an undirected graph.
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.
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.
See also
Other flow:
dominator_tree()
,
edge_connectivity()
,
is_min_separator()
,
is_separator()
,
max_flow()
,
min_cut()
,
min_separators()
,
st_cuts()
,
st_min_cuts()
,
vertex_connectivity()
Author
Gabor Csardi csardi.gabor@gmail.com
Examples
ring <- make_ring(4)
min_st_separators(ring)
#> [[1]]
#> + 2/4 vertices, from 2205838:
#> [1] 2 4
#>
#> [[2]]
#> + 2/4 vertices, from 2205838:
#> [1] 1 3
#>
chvatal <- make_graph("chvatal")
min_st_separators(chvatal)
#> [[1]]
#> + 4/12 vertices, from 832c600:
#> [1] 7 10 11 12
#>
#> [[2]]
#> + 4/12 vertices, from 832c600:
#> [1] 3 6 8 11
#>
#> [[3]]
#> + 4/12 vertices, from 832c600:
#> [1] 2 7 9 12
#>
#> [[4]]
#> + 4/12 vertices, from 832c600:
#> [1] 8 10 11 12
#>
#> [[5]]
#> + 4/12 vertices, from 832c600:
#> [1] 6 9 11 12
#>
#> [[6]]
#> + 4/12 vertices, from 832c600:
#> [1] 2 5 7 10
#>
#> [[7]]
#> + 4/12 vertices, from 832c600:
#> [1] 1 3 6 8
#>
#> [[8]]
#> + 4/12 vertices, from 832c600:
#> [1] 2 4 7 9
#>
#> [[9]]
#> + 4/12 vertices, from 832c600:
#> [1] 3 5 8 10
#>
#> [[10]]
#> + 4/12 vertices, from 832c600:
#> [1] 1 4 6 9
#>
#> [[11]]
#> + 4/12 vertices, from 832c600:
#> [1] 1 2 4 5
#>
#> [[12]]
#> + 4/12 vertices, from 832c600:
#> [1] 1 3 4 5
#>
#> [[13]]
#> + 6/12 vertices, from 832c600:
#> [1] 3 6 8 10 11 12
#>
#> [[14]]
#> + 6/12 vertices, from 832c600:
#> [1] 4 6 7 9 11 12
#>
#> [[15]]
#> + 6/12 vertices, from 832c600:
#> [1] 2 4 5 7 10 12
#>
#> [[16]]
#> + 6/12 vertices, from 832c600:
#> [1] 3 4 5 7 10 11
#>
#> [[17]]
#> + 6/12 vertices, from 832c600:
#> [1] 6 7 8 9 11 12
#>
#> [[18]]
#> + 6/12 vertices, from 832c600:
#> [1] 3 5 7 8 10 11
#>
#> [[19]]
#> + 6/12 vertices, from 832c600:
#> [1] 3 4 6 7 9 11
#>
#> [[20]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 3 4 5 6 8
#>
#> [[21]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 6 8 9 12
#>
#> [[22]]
#> + 6/12 vertices, from 832c600:
#> [1] 2 5 7 8 10 12
#>
#> [[23]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 4 5 7 9
#>
#> [[24]]
#> + 6/12 vertices, from 832c600:
#> [1] 2 7 9 10 11 12
#>
#> [[25]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 6 8 9 11 12
#>
#> [[26]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 5 8 10 12
#>
#> [[27]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 3 5 8 10 11
#>
#> [[28]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 4 6 9 12
#>
#> [[29]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 3 4 6 9 11
#>
#> [[30]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 3 5 8 10
#>
#> [[31]]
#> + 6/12 vertices, from 832c600:
#> [1] 1 2 3 4 6 9
#>
#> [[32]]
#> + 6/12 vertices, from 832c600:
#> [1] 2 3 4 5 7 10
#>