welcome: please sign in
location: Diff for "ProblemsDescription/MaximalClique"
Differences between revisions 1 and 3 (spanning 2 versions)
⇤ ← Revision 1 as of 2011-01-05 13:18:55 →
Size: 971
Editor: CarmenSantoro
Comment:
← Revision 3 as of 2011-01-10 10:06:19 → ⇥
Size: 1093
Editor: CarmenSantoro
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
'''Maximal Clique''' = Maximal Clique =
Line 3: Line 3:
Problem description <<TableOfContents>>

== Problem Description ==
Line 7: Line 9:
Input format == Input format ==
Line 15: Line 17:
Output format == Output format ==
Line 22: Line 24:

== Example ==

== Author(s) ==
Author: Johan Wittocx
<<BR>>
Affiliation:

Maximal Clique

Contents

  1. Maximal Clique
    1. Problem Description
    2. Input format
    3. Output format
    4. Example
    5. Author(s)

Problem Description

This is the problem of finding a maximal clique C in an undirected graph G. I.e., for each other clique C' in G, the number of nodes in C should be larger than the number of nodes in C'.

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:

ASP Competition 2011: ProblemsDescription/MaximalClique (last edited 2011-01-10 11:13:17 by CarmenSantoro)