grinpy.invariants.independence.max_independent_set¶
-
grinpy.invariants.independence.
max_independent_set
(G)¶ Return a largest independent set of nodes in G.
The method used is a modified brute force search. The search starts with subsets of G with cardinality equal to the annihilation number of G, which was shown by Pepper to be an upper bound for the independence number of a graph, and then continues checking smaller subsets until a maximum independent set is found.
Parameters: G (NetworkX graph) – An undirected graph. Returns: A list of nodes comprising a largest independent set in G. Return type: list See also