Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.approximation.independent_set.maximum_independent_set

maximum_independent_set(G)

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.