grinpy.invariants.independence.max_k_independent_set¶
-
grinpy.invariants.independence.max_k_independent_set(G, k)¶ Return a largest k-independent set of nodes in G.
The method used is brute force, except when k*=1. In this case, 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.
- k : int
- A positive integer.
- maxKIndependentSet : list
- A list of nodes comprising a largest k-independent set in G.
max_independent_set