RT - article
SR - Electronic
T1 - Задача о ({K1, K2},k,l)-упаковке наибольшего веса в графе
JF - Известия Национальной академии наук Беларуси. Серия физико-математических наук
SP - 2023-07-06
DO - 10.29235/1561-2430-2023-59-2-121-129
A1 - Лепин В. В., 
YR - 2023
UL - https://www.academjournals.by/publication/12690
AB - Рассматривается задача о ({K1,K2},k,l)-упаковке наибольшего веса в графе, которая обобщает ряд известных задач, например, о независимом множестве, максимальном индуцированном паросочетании, k-разделенном паросочетании, связном паросочетании, диссоциирующем множестве, k-упаковке. Показано, что в классе кографов ({K1,K2},k,l)-упаковку наибольшего веса можно найти за время O(n + m). Пусть Г – класс графов и Г* – класс всех простых (относительно модульной декомпозиции) порожденных подграфов из Г. Доказано, что если задача об оптимальной ({K1,K2},k,l)-упаковке графа может быть решена в классе графов Г* за время O(np ), где p ≥ 2 – константа, то эта задача может быть решена в классе графов Г за время O(np ).