Maximum clique algorithms

Témavezető:	Madarasi Péter
	ELTE TTK, Operációkutatási Tsz.
email:	madarasip@staff.elte.hu

Projekt leírás

The most efficient maximum clique algorithms are based on the Branch&Bound framework. They try to find the nodes of a largest clique in a backtracking fashion, and they compute an upper bound on the size of the largest clique in the current branch of the search. This bound is typically the number of colors used by a greedily proper vertex coloring.

This project aims to strengthen the coloring-based bound, and implement an efficient maximum clique algorithm.

Előfeltételek

Low-level programming experience (or irresistible desire to delve into it) is a must. Experience in C++ is a plus.

Hivatkozások

[1] Tomita, E., Matsuzaki, S., Nagao, A., Ito, H. and Wakatsuki, M., 2017. A much faster algorithm for finding a maximum clique with computational experiments. Journal of Information Processing, 25, pp.667-677.