Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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|).
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
9--21
Opis fizyczny
Twórcy
autor
- Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland
Bibliografia
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-3606a903-e23c-439d-b720-5e9f4f51a4cb