9.3.2007: HIIT seminar

HIIT seminars in spring 2007 will be held in hall **B222** of Exactum,
on Fridays starting at 10:15 a.m. Coffee available from 10.

Fri Mar 9
Patric Östergård
Russian Doll Search for Maximum Clique and Similar Problems

Abstract:
A clique in a graph is a set of vertices that are mutually adjacent. Several important problems in areas like computational systems biology and telecommunications theory, just to mention two, are related to cliques (or, equivalently, independent sets) in graphs. A Russian doll search algorithm for the maximum clique problem is considered in this presentation. This algorithm can be further generalized to the case of vertex-weighted graphs and the maximum-weight clique problem; an implementation (in C), called Cliquer, is available at . Algorithms for some other similar problems are also briefly discussed, including the combinatorial best barbeque problem, which arises in the context of discovering cis-regulatory modules in regulatory DNA sequences.