Algorithms for the Weighted $k$-Path Vertex Cover Problem for Trees and Cacti

Rastislav Krivoš Belluš
P. J. Šafárik University in Košice, Slovakia

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: $k$-Path Vertex Cover Problem is NP-hard for several classes of graphs. We have focused on the weighted version of this problem. We will analyze complexity of exact algorithms for finding minimum $k$-Path Vertex Cover for trees and cacti graphs using dynamic programming and with parametrized complexity depending on its girth.

Back to all abstracts