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