НЕПЕРЕСЕКАЮЩИЕСЯ КОНФИГУРАЦИИ В ДОПОЛНЕНИЯХ ГЕОМЕТРИЧЕСКИХ ГРАФОВ И ДИЗЪЮНКТНАЯ СОВМЕСТИМОСТЬ
2016
В работе для произвольного непересекающегося совершенного паросочетания за время O(n4 log n) строится дизъюнктно совместимое остовное дерево максимальной степени вершин не больше 4. Получен критерий существования непересекающегося совершенного паросочетания в дополнении звезды порядка меньше 2n в K2n. Доказано существование непересекающегося совершенного паросочетания в дополнении дерева порядка (n + 1) в K2n с числом внутренних вершин, не превышающим (n – 1).
БЕНЕДИКТОВИЧ В. И. НЕПЕРЕСЕКАЮЩИЕСЯ КОНФИГУРАЦИИ В ДОПОЛНЕНИЯХ ГЕОМЕТРИЧЕСКИХ ГРАФОВ И ДИЗЪЮНКТНАЯ СОВМЕСТИМОСТЬ. Доклады Национальной академии наук Беларуси. 2016;60(4):8-16.
Цитирование
Список литературы