Independent vertex sets
A vertex set is called independent if there no edges between any two vertices in it. These functions find independent vertex sets in undirected graphs
independent.vertex.sets(graph, min=NULL, max=NULL) largest.independent.vertex.sets(graph) maximal.independent.vertex.sets(graph) independence.number(graph)
- The input graph, directed graphs are considered as undirected, loop edges and multiple edges are ignored.
- Numeric constant, limit for the minimum size of the
independent vertex sets to find.
NULLmeans no limit.
- Numeric constant, limit for the maximum size of
the independent vertex sets to find.
NULLmeans no limit.
independent.vertex.sets finds all independent vertex sets in
the network, obeying the size limitations given in the
largest.independent.vertex.sets finds the largest independent
vertex sets in the graph. An independent vertex set is largest if
there is no independent vertex set with more vertices.
maximal.independent.vertex.sets finds the maximal independent
vertex sets in the graph. An independent vertex set is maximal if it
cannot be extended to a larger independent vertex set. The largest
independent vertex sets are maximal, but the opposite is not always
independece.number calculate the size of the largest
independent vertex set(s).
These functions use the algorithm described by Tsukiyama et al., see reference below.
maximal.independent.vertex.setsreturn a list containing numeric vertex ids, each list element is an independent vertex set.
independence.numberreturns an integer constant.
Independent vertex set
S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.
# A quite dense graph g <- erdos.renyi.game(100, 0.8) independence.number(g) independent.vertex.sets(g, min=independence.number(g)) largest.independent.vertex.sets(g) # Empty graph subgraph(g, largest.independent.vertex.sets(g)[]) length(maximal.independent.vertex.sets(g))