The Maximum Clique problem in graphs asks for a clique of maximum size, a clique being a subset of nodes such that each node is connected to all other nodes of the subset.

[Example Graph]

As an example, the image above shows a graph of 10 nodes, with a (red) clique of size 4.

The following is an example of a graph of 10 nodes (see above figure) given in the DIMACS format.
The first character of each line describes the information:

c The following lines are all comments
c number of vertices  : 10
c nonisolated vertices: 9
c number of edges     : 18
c This is the last comment line
p clq 10 18
e 1 3
e 1 5
e 2 3
e 2 4
e 2 8
e 3 4
e 3 5
e 3 6
e 4 5
e 4 6
e 5 6
e 5 9
e 6 8
e 7 5
e 7 6
e 7 8
e 7 9
e 8 9

© 2005-2009 Roberto Battiti and Mauro Brunato, All Rights Reserved.
Pages hosted by "machine Learning and Intelligent Optimization (LION)" Group - DISI - Università di Trento - Italy.
Last updated: 2012-03-15 07:05:40