A Continuous-Based Approach for Partial Clique Enumeration

author: Samuel Rota Bulo, University Ca' Foscari
published: July 4, 2007,   recorded: June 2007,   views: 3378

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


In many applications of computer vision and pattern recog- nition which use graph-based knowledge representation, it is of great interest to be able to extract the K largest cliques in a graph, but most methods are geared either towards extracting the single clique of max- imum size, or enumerating all cliques, without following any particular order. In this paper we present a novel approach for partial clique enu- meration, that is, the extraction of the K largest cliques of a graph. Our approach is based on a continuous formulation of the clique problem de- veloped by Motzkin and Straus, and is able to avoid extracting the same clique multiple times. This is done by casting the problem into a game- theoretic framework and iteratively rendering unstable the solutions that have already been extracted.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: