min_st_separators: Minimum size vertex separators

In igraph: Network Analysis and Visualization

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

Related documentation in the C library

igraph_all_minimal_st_separators().

Author(s)

Gabor Csardi [e-mail]

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

igraph documentation built on Oct. 20, 2024, 1:06 a.m.