On the weightedk-path vertex cover on interval graphs

Jakub  Zygadło

On the weightedk-path vertex cover on interval graphs

Publication date: 2020

Schedae Informaticae, First View 2020, Volume 29, pp. 9-21

https://doi.org/10.4467/20838476SI.20.001.14380

Authors

Download full text

print cite

Titles

On the weightedk-path vertex cover on interval graphs

Abstract

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|).

Keywords

k-path vertex cover, interval graph, weighted graph, dynamic programming

Information

Information: Schedae Informaticae, First View 2020, Volume 29, pp. 9-21

DOI: https://doi.org/10.4467/20838476SI.20.001.14380

Article type: Original scientific article

Authors

Jakub Zygadło

Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland

Published at: 2020

Article status: Open

Licence: CC BY 4.0

Percentage share of authors:

Jakub Zygadło (Author) - 100%

Article corrections:

Publication languages:

English

View count: 812

Number of downloads: 0

<p>On the weightedk-path vertex cover on interval graphs</p>

Download xml