TY - JOUR
TI - On the weightedk-path vertex cover on interval graphs
AU - Zygadło, Jakub
TI - On the weightedk-path vertex cover on interval graphs
AB - 
	We consider a version of the k-path vertex cover problem that asks for the minimum weight subset C of vertices of a graph G such that every path on k vertices in G has at least one vertex in common with C. We present two dynamic algorithms solving this problem on interval graphs. The first one works on general interval graphs but is in practice limited to small values of k.
	The second algorithm computes minimum weight vertex cover for arbitrary k on proper interval graph G = (V,E) in time O(|V|^2|E|).
VL - First View 2020
IS - Volume 29
PY - 2020
SN - 1732-3916
C1 - 2083-8476
SP - 9
EP - 21
DO - 10.4467/20838476SI.20.001.14380
UR - https://ejournals.eu/en/journal/schedae-informaticae/article/on-the-weightedk-path-vertex-cover-on-interval-graphs
KW - k-path vertex cover
KW - interval graph
KW - weighted graph
KW - dynamic programming