Loading [Contrib]/a11y/accessibility-menu.js
  1. CSPLib
  2. Problems
  3. prob074
  4. Models
  5. naive-maxclique.essence

074: Maximum Clique

Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ Maximum Clique Problem (CSPLib 074)
$ Naive model for a largest clique in a graph presented as a list of edges.
$ Edges are pairs of vertices in a relation; (u,v) is interpreted as {u,v}.
$ Vertices are numbered 1 to n, all are regarded as part of the graph.
$
$ Andras Salamon <Andras.Salamon@st-andrews.ac.uk>
$ 2017-07-07
 
language Essence 1.3
letting n be 5
letting vertices be domain int(1..n)
letting G be relation((1,2),(1,4),(2,3),(3,4),(3,5),(4,5))
 
find C : matrix indexed by [vertices] of bool $ vertices in clique
find size : vertices $ number of vertices in the clique
 
$ the clique includes at most one of any pair of non-neighbouring vertices
such that
size = sum([toInt(C[u]) | u : vertices]),
forAll v : int(2..n) . forAll u : int(1..(v-1)) .
    (!((u,v) in G) /\ !((v,u) in G)) -> (!C[u] \/ !C[v])
 
maximising size