Решение задачи о взвешенной независимой $\{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\}$-упаковки наибольшего веса.
Представлен алгоритм, который решает задачу о взвешенной независимой $\{K_1,K_2\}$-упаковке графа в классе древесных кографов. Временная сложность алгоритма $O(m),$ где $m=|E(G)|.$