The Maximum Clique Problem and its Applications

<div>We have considered three recent branch and bound algorithms: MCS algorithm by Tomita et al (2010), MAXSAT algorithm by Li and Quan (2010a) and BBMCXRS algorithm by Segundo and Tapia. We suggest using ILS heuristic (Andrade et al, 2012) to obtain an initial high-quality solution which is then used to prune branches in the main branch and bound algorithm. The computational study shows that this improvement results in a considerable reduction of the search tree size and computational time for all considered algorithms. Also, we develop our algorithm for the maximum clique problem (Maslov et al., 2013) and apply it to the protein structure alignment problem using the DAST approach to reduce the alignment problem to the MCP. Our algorithm is based on the MCS algorithm recently published by Tomita et al. (2010). We significantly improve the performance of the MCS algorithm. The suggested algorithm is also at least comparable with the ACF algorithm applied in the DAST tool (which is the fastest exact algorithms for the PSAP to the best of our knowledge) and much better than Ostergard, MCS, MAXSAT and BBMCXRS algorithms</div>