igraph (version 1.3.5)

min_st_separators: 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)

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\).

Arguments

graph

The input graph. It may be directed, but edge directions are ignored.

Author

Gabor Csardi

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.

Examples

ring <- make_ring(4)
min_st_separators(ring)

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