Affordable Access

Reactive and dynamic local search for Max-Clique, does the complexity pay off?

Publication Date
  • Q360 Information Theory
  • Qa075 Electronic Computers. Computer Science
  • Qa076 Computer Software
  • Computer Science


This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Maximum Clique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.

There are no comments yet on this publication. Be the first to share your thoughts.