Pablo San Segundo (Universidad Politecnica de Madrid (UPM), Madrid, Spain): Upper bounds for the maximum clique problem

The Maximum Clique Problem is a fundamental NP-hard problem in graph theory which finds numerous real-life applications. In the last decade a number of new upper bounds and implementation techniques have come to light, which have improved the performance of prior exact solvers by orders of magnitude. The relevance of these improvements is shifting the attention of researchers to solve other fundamental combinatorial problems and applications by reducing them to a maximum clique problem. In this talk, some of the cutting edge improvements concerning exact maximum clique search will be discussed. Special attention will be devoted to the relation of these techniques with other combinatorial problems. At the end of the talk we will discuss how different combinatorial problems can combine to solve a constraint-satisfacton problem