Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
max_clique¶
- max_clique(G)[source]¶
Find the Maximum Clique
Finds the \(O(|V|/(log|V|)^2)\) apx of maximum clique/independent set in the worst case.
Parameters : G : NetworkX graph
Undirected graph
Returns : clique : set
The apx-maximum clique of the graph
Notes
A clique in an undirected graph G = (V, E) is a subset of the vertex set \(C \subseteq V\), such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).
A maximum clique is a clique of the largest possible size in a given graph. The clique number \(\omega(G)\) of a graph G is the number of vertices in a maximum clique in G. The intersection number of G is the smallest number of cliques that together cover all edges of G.
http://en.wikipedia.org/wiki/Maximum_clique
References
[R139] Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer. doi:10.1007/BF01994876