RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2017 Volume 25, Number 1, Pages 62–81 (Mi timb269)

The weighted $k$-path vertex cover problem on series-parallel graphs

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{R}^+$ and a positive integer $k,$ we consider the weighted $k$-path vertex cover problem: it consists in finding a minimum-weight subset $S$ of vertices of a graph $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S.$ We give $O(n)$ algorithms for finding the minimum weight of $k$-path vertex cover and connected $k$-path vertex cover for series-parallel graphs.

UDC: 519.1

Received: 10.01.2017



© Steklov Math. Inst. of RAS, 2025