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