|
⇤ ← Revision 1 as of 2011-01-19 09:34:07
Size: 770
Comment:
|
Size: 1665
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Predicates == * '''Input''': node/1, edge/2 * '''Output''': clique/1 |
|
| Line 6: | Line 12: |
* Input Predicates: node/1, edge/2 * Output Predicates: clique/1 |
|
| Line 14: | Line 16: |
== Input format == As input, a directed graph is given. A solution is the largest clique in the symmetric closure of this input graph. The nodes of the input graph are given by facts of the form node(i). The edges of the graph are given by facts of the form edge(i,j). The following is an example input: node(1). node(2). node(3). node(4). node(5). node(6). edge(1,2). edge(1,5). edge(2,3). edge(2,5). edge(3,4). edge(4,5). edge(4,6). == Output format == The output should consist of a set of facts of the form clique(i). The set of all 'i' that appear in such a fact, should form a maximal clique in the symmetric closure of the input graph. For the above example, the only correct output is clique(1). clique(2). clique(5). == Example == == Author(s) == Author: Johan Wittocx <<BR>> Affiliation: Department of Computer Science, K.U.Leuven, Belgium |
Maximal Clique Problem
Contents
Predicates
Input: node/1, edge/2
Output: clique/1
Problem Description
This is the problem of finding a maximal clique C in an undirected graph G. That is, for each other clique C' in G, the number of nodes in C should be larger than or equal to the number of nodes in C'.
As input, a directed graph is given, encoded by facts over the predicates node/1 and edge/2, providing respectively the nodes and the edges. A solution to the problem is a maximal clique in the undirected version of the input graph (i.e., in the symmetric closure of the input graph). A solution is encoded by the predicate clique/1: the set of nodes v such that clique(v) holds should form a maximal clique.
Input format
As input, a directed graph is given. A solution is the largest clique in the symmetric closure of this input graph. The nodes of the input graph are given by facts of the form node(i). The edges of the graph are given by facts of the form edge(i,j).
The following is an example input: node(1). node(2). node(3). node(4). node(5). node(6). edge(1,2). edge(1,5). edge(2,3). edge(2,5). edge(3,4). edge(4,5). edge(4,6).
Output format
The output should consist of a set of facts of the form clique(i). The set of all 'i' that appear in such a fact, should form a maximal clique in the symmetric closure of the input graph.
For the above example, the only correct output is clique(1). clique(2). clique(5).
Example
Author(s)
Author: Johan Wittocx
Affiliation: Department of Computer Science, K.U.Leuven, Belgium