Алгоритмы решения задачи реализации запросов для деревьев и последовательно-параллельных графов

Рассматривается $k$-SHP (Star Hub Problem) задача:
Вход: дан граф $G=(V,E)$, весовая функция $w_0\colon E\to\mathbb{Z}^+$ на ребрах и $k$ весовых функций на вершинах: $w_1,\ldots,w_k$, где $w_i\colon V\to \mathbb{Z}^+$ для $i=1,\ldots,k$.
Цель: найти множество ребер $F\subseteq E$ и $k$ подмножеств вершин $V_1,\ldots,V_k\subseteq V$ такие, что для каждого ребра $e=(u,v)\in E$ либо $e\in F$, либо для некоторого $i\in\{1,\ldots,k\}$ $\{u,v\}\in V_i$, и целевая функция
$$ \sum_{e\in F}w_0(e)+\sum_{i=1}^k\,\sum_{v\in V_i}w_i(v) $$
принимает наименьшее значение.
Показано, что при фиксированном $k>1$ эта задача решается за линейное время в классе деревьев и последовательно-параллельных графов.
Библиогр. 8 назв.