networkx.algorithms.approximation.independent_set.maximum_independent_set¶
-
maximum_independent_set
(G)[source]¶ Returns an approximate maximum independent set.
- Parameters
G (NetworkX graph) – Undirected graph
- Returns
iset – The apx-maximum independent set
- Return type
Set
Notes
Finds the \(O(|V|/(log|V|)^2)\) apx of independent set in the worst case.
References
- 1
Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.