|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Теоретические основы информатики
Improved upper bounds in clique partitioning problem
[Улучшенные верхние оценки в задаче оптимального разбиения графа на клики]
A. B. Belyia, S. L. Sobolevskiibcd, A. N. Kourbatskie, C. Rattic a SMART Centre, 1 Create Way, Singapore 138602, Singapore
b ITMO University, 49 Kronverksky Avenue, Saint Petersburg 197101, Russia
c Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge 02139, USA
d New York University, 370 Jay Street, New York 11201, USA
e Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus
Аннотация:
Рассматривается задача нахождения разбиения полного взвешенного графа на клики так, что сумма весов ребер между вершинами, принадлежащими одной клике, максимальна. Данная задача, известная как задача разбиения графа на клики (clique partitioning problem), возникает во многих приложениях и представляет собой вариант классической задачи кластеризации. Она, как и многие другие задачи комбинаторной оптимизации, является $NP$-трудной, поэтому нахождение ее точного решения зачастую оказывается трудоемким. В данной работе предлагается новый метод построения верхней оценки для функции качества разбиения и показывается, как полученная оценка применяется в методе ветвей и границ при нахождении точного решения. Предлагаемый подход накладывает ограничения на максимально возможное качество разбиения. Новизна метода заключается в возможности
использования треугольников, пересекающихся по ребрам, что позволяет находить гораздо более точные оценки, чем при рассмотрении только непересекающихся подграфов. Помимо построения начальной оценки в статье описывается способ ее пересчета при фиксировании ребер на каждом шаге метода ветвей и границ. Приводятся результаты тестирования предлагаемого алгоритма на сгенерированных наборах случайных графов. Показывается, что версия, использующая новые оценки, работает в несколько раз быстрее ранее известных методов
Ключевые слова:
разбиение графа на клики; точное решение; метод ветвей и границ; верхние оценки.
Поступила в редакцию: 26.08.2019
Образец цитирования:
A. B. Belyi, S. L. Sobolevskii, A. N. Kourbatski, C. Ratti, “Improved upper bounds in clique partitioning problem”, Журн. Белорус. гос. ун-та. Матем. Инф., 3 (2019), 93–104
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/bgumi107 https://www.mathnet.ru/rus/bgumi/v3/p93
|
Статистика просмотров: |
Страница аннотации: | 49 | PDF полного текста: | 34 | Список литературы: | 9 |
|