maximum_independent_set¶
-
maximum_independent_set
(G)[source]¶ Return 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.