k-path partition and k-path vertex cover
RNDr. Rastislav Krivoš-Belluš, PhD.
Ústav informatiky, 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.
- Ch. Brause, R. Krivoš-Belluš, On a relation between k-path partition and k-path vertex cover, In In press in Discrete Appl. Mathematics, http://dx.doi.org/10.1016/j.dam.2017.01.013