clique_removal¶
- clique_removal(G)[source]¶
Repeatedly remove cliques from the graph.
Results in a \(O(|V|/(\log |V|)^2)\) approximation of maximum clique and independent set. Returns the largest independent set found, along with found maximal cliques.
- Parameters
- GNetworkX graph
Undirected graph
- Returns
- max_ind_cliques(set, list) tuple
2-tuple of Maximal Independent Set and list of maximal cliques (sets).
- Raises
- NetworkXNotImplemented
If the graph is directed or is a multigraph.
References
- 1
Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.