Взвешенная задача о покрытии $k$-цепей последовательно-параллельного графа

Если дан граф $G$ с весовой функцией $\omega:~V(G)\to\mathbb{R}^+,$ то весом подмножества вершин $U\subseteq V(G)$ называется $\omega(U)=\sum_{v\in U}\omega(v).$ Рассматривается задача нахождения наименьшего веса подмножества вершин $W$ такого, что каждая цепь длины $k$ содержит, по крайней мере, одну вершину из $W.$ Такое подмножество называется покрытием $k$-цепей графа $G.$ Рассматривается также задача нахождения наименьшего веса подмножества вершин $W$ такого, что порожденный на $W$ подграф является связным и каждая цепь длины $k$ содержит, по крайней мере, одну вершину из $W.$ Представлены алгоритмы, которые решают взвешенную задачу о покрытии $k$-цепей и взвешенную задачу о связном покрытии $k$-цепей в классе последовательно-параллельных графов. Временная сложность алгоритмов $O(n),$ где $n$ — число вершин графа.