|
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.
Received: 10.01.2017
Citation:
V. V. Lepin, “The weighted $k$-path vertex cover problem on series-parallel graphs”, Tr. Inst. Mat., 25:1 (2017), 62–81
Linking options:
https://www.mathnet.ru/eng/timb269 https://www.mathnet.ru/eng/timb/v25/i1/p62
|
| Statistics & downloads: |
| Abstract page: | 585 | | Full-text PDF : | 330 | | References: | 187 |
|