| min_st_separators {igraph} | R Documentation |
Minimum size vertex separators
Description
List all vertex sets that are minimal (s,t) separators for some
s and t, in an undirected graph.
Usage
min_st_separators(graph)
Arguments
graph |
The input graph. It may be directed, but edge directions are ignored. |
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 proper subsets is
an (s,t) vertex separator for the same s and t.
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.
Note
Note that the code below returns {1, 3} despite its subset {1} being a
separator as well. This is because {1, 3} is minimal with respect to
separating vertices 2 and 4.
g <- make_graph(~ 0-1-2-3-4-1) min_st_separators(g)
#> [[1]] #> + 1/5 vertex, named: #> [1] 1 #> #> [[2]] #> + 2/5 vertices, named: #> [1] 2 4 #> #> [[3]] #> + 2/5 vertices, named: #> [1] 1 3
Author(s)
Gabor Csardi csardi.gabor@gmail.com
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()
Examples
ring <- make_ring(4)
min_st_separators(ring)
chvatal <- make_graph("chvatal")
min_st_separators(chvatal)
# https://github.com/r-lib/roxygen2/issues/1092