• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Evgenij Maslov
The Maximum Clique Problem and its Applications
Master’s programme
2014
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

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses