|
Труды Института математики, 2022, том 30, номер 1-2, страницы 44–49
(Mi timb333)
|
|
|
|
Применение декомпозиции по минимальным кликовым разделителям для нахождения $\{K_1,K_2,k,l\}$-упаковки наибольшего веса в графе
В. В. Лепин Институт математики НАН Беларуси
Аннотация:
Рассматривается задача о $(\{K_{1},K_{2}\},k,l)$-упаковке наибольшего веса в графе, которая обобщает ряд известных задач, например: о независимом множестве; о максимальном индуцированном паросочетании; о $k$-разделенном паросочетании; о связном паросочетании; о диссоциирующем множестве; о $k$-упаковке. Пусть $\Gamma$ – класс графов и $\Gamma^*$ – класс всех порожденных подграфов из $\Gamma$ являющимися атомами относительно декомпозиции по минимальным кликовым разделителям. Доказано, что если задача об оптимальной $(\{ K_{1} ,K_{2} \} ,k,l)$-упаковке графа может быть решена в классе графов $\Gamma^*$ за время $O(f_{atoms}(n)),$ то эта задача может быть решена в классе графов $\Gamma$ за время $O(n(n+m)\cdot f_{atoms}(n)).$
Поступила в редакцию: 18.11.2022
Образец цитирования:
В. В. Лепин, “Применение декомпозиции по минимальным кликовым разделителям для нахождения $\{K_1,K_2,k,l\}$-упаковки наибольшего веса в графе”, Тр. Ин-та матем., 30:1-2 (2022), 44–49
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timb333 https://www.mathnet.ru/rus/timb/v30/i1/p44
|
Статистика просмотров: |
Страница аннотации: | 112 | PDF полного текста: | 41 | Список литературы: | 25 |
|