min_st_separators

0th

Percentile

Minimum size vertex separators

List all vertex sets that are minimal (s,t) separators for some s and t, in an undirected graph.

Keywords
graphs
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 subsets is an $(s,t)$ vertex separator.

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$.

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.

Aliases
• min_st_separators
• minimal.st.separators
Examples
# NOT RUN {
ring <- make_ring(4)
min_st_separators(ring)

chvatal <- make_graph("chvatal")
min_st_separators(chvatal)
# }

Documentation reproduced from package igraph, version 1.2.4.1, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.