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.