Seminár Ústavu informatiky


k-path partition and k-path vertex cover

RNDr. Rastislav Krivoš-Belluš, PhD.
Ústav informatiky, PF UPJŠ

20. decembra 2017 (streda) o 12:45
SJ2S07 (3.16T), PF UPJŠ


Motivated by the problem of ensuring data integrity of communication in wireless sensor networks using the k-generalised Canvas scheme Brešar et al. introduced the minimum  k-path vertex cover problem (MkPVCP), a generalisation of the minimum vertex cover problem . Although it is a new problem in graph theory, many people have spent a lot of effort in studying it. The problem is known to be NP-hard.

In this presentation, we present several algorithms solving MkPVCP, also for the weighted version of the problem. Afterwards we will focus on the relation of the MkPVCP with the minimum k-path partition problem. Recently we have obtained new bounds for their invariants and a new sufficient condition for NP-hardness of the MkPVCP in terms of forbidden subgraphs.