7.1.6.1. networkx.algorithms.approximation.independent_set.maximum_independent_set¶

networkx.algorithms.approximation.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

[R458]

Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.