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.
- G : graph
- A Networkx graph.
- maxIndependentSet : list
- A list of nodes comprising a largest independent set in G.
max_independent_set