• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Маслов Евгений Валерьевич
The Maximum Clique Problem and its Applications
Магистратура
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

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР