В.А.Любецкий, А.В.Селиверстов

Многодольные графы с двумя вершинами в каждой доле

В работе рассмотрен алгоритм поиска клики в многодольном графе с двумя вершинами в каждой доле. Отметим, что это позволяет решить частный случай задачи выравнивания, т.е. поиска набора похожих слов, по одному слову в каждой из n пар. Обсуждается сложность описания политопа клик.