NetworkX

Previous topic

min_edge_dominating_set

Next topic

min_maximal_matching

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

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