Решение задачи о взвешенной независимой $\{K_1,K_2\}$-упаковке на графах со специальными блоками

Пусть $\mathcal{H}$ — фиксированное множество связных графов. $\mathcal{H}$-упаковкой графа $G$ называется множество $\mathcal{S}=\{G_1,G_2,\ldots,G_m\}$ попарно не пересекающихся подграфов графа $G,$ каждый из которых изоморфен графу из $\mathcal{H}.$ Независимой $\mathcal{H}$-упаковкой графа $G$ называется $\mathcal{H}$-упаковка $S,$ в которой никакие два подграфа упаковки не соединены ребром графа $G.$ Если дан граф $G$ с весовыми функциями $\omega_V:~V(G)\to\mathbb{N}$ и $\omega_E:~E(G)\to\mathbb{N}$ на вершинах и ребрах и независимая $\{K_1,K_2\}$-упаковка $S$ графа $G,$ то весом $S$ называется $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ где $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i)$ и $F=\bigcup_{G_i\in\mathcal{S}}E(G_i).$ Рассматривается задача нахождения независимой $\{K_1,K_2\}$-упаковки наибольшего веса. Представлен алгоритм, который решает эту задачу для графов, у которых каждый блок является либо кликой, либо циклом, либо полным двудольным графом. Этот класс графов включает деревья, блочные графы, кактусы и блочно-кактусовые графы. Временная сложность алгоритма $O(n^2m),$ где $n=|V(G)|$ и $m=|E(G)|$.