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.
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:
- `p` starts the problem line (the two numbers are no. of nodes and no. of edges in the graph)
- `e` describes a single edge (first node is 1)
- `c` is a comment
- `clq` in the problem line states that this is a Max Clique problem.
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
Pages hosted by "machine Learning and Intelligent Optimization (LION)" Group - DISI - Università di Trento - Italy.
Last updated: 2012-03-15 07:05:40
![[Reactive Search Logo]](images/logo.jpg)
