welcome: please sign in
location: Diff for "FinalProblemDescriptions/MaximalClique"
Differences between revisions 2 and 4 (spanning 2 versions)
⇤ ← Revision 2 as of 2011-01-19 16:36:03 →
Size: 1665
Editor: CarmenSantoro
Comment:
← Revision 4 as of 2011-02-01 16:15:20 → ⇥
Size: 1942
Editor: CarmenSantoro
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:

== Predicates ==

 * '''Input''': node/1, edge/2

 * '''Output''': clique/1
Line 15: Line 9:
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. 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.

== Predicates ==

 * '''Input''': {{{node/1, edge/2}}}

 * '''Output''': {{{clique/1}}}
Line 19: Line 19:
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).		 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)}}}.
Line 23: Line 22:
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). {{{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).}}}
Line 27: Line 26:
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.		 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.
Line 30: Line 28:
For the above example, the only correct output is
clique(1). clique(2). clique(5).		 For the above example, the following are two correct outputs:
 * {{{clique(1). clique(2). clique(5).}}}
 * {{{clique(1). clique(2).}}}
Line 33: Line 32:
== Example == The first is better than the second (in fact, the first is the maximal clique).

== Example(s) ==

== Notes and Updates ==

 * Specification: updated "Output format" section on date 01/02/2011;
Line 36: Line 41:
Author: Johan Wittocx
<<BR>>
Affiliation: Department of Computer Science, K.U.Leuven, Belgium		  * Author: Johan Wittocx
   * Affiliation: Department of Computer Science, K.U.Leuven, Belgium

Maximal Clique Problem

Contents

  1. Maximal Clique Problem
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Notes and Updates
    7. Author(s)

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.

Predicates

  • Input: node/1, edge/2

  • Output: clique/1

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 following are two correct outputs:

  • clique(1). clique(2). clique(5).

  • clique(1). clique(2).

The first is better than the second (in fact, the first is the maximal clique).

Example(s)

Notes and Updates

  • Specification: updated "Output format" section on date 01/02/2011;

Author(s)

  • Author: Johan Wittocx
    • Affiliation: Department of Computer Science, K.U.Leuven, Belgium

ASP Competition 2011: FinalProblemDescriptions/MaximalClique (last edited 2011-07-20 14:27:09 by GiovambattistaIanni)