NetworkX

Previous topic

min_weighted_vertex_cover

Next topic

clique_removal

max_clique

max_clique(graph)[source]

Find the Maximum Clique

Finds the O(|V|/(log|V|)^2) apx of maximum clique/independent set in the worst case.

Parameters :

graph : 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

[R104]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