welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

Revision 1 as of 2011-01-19 09:34:07

location: FinalProblemDescriptions / MaximalClique

Maximal Clique Problem

Contents

  1. Maximal Clique Problem
    1. Problem Description

Problem Description

* Input Predicates: node/1, edge/2

* Output Predicates: clique/1

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.