Approximability and parameterized complexity of multicover by c-intervals

René Van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger

Результат исследования: Научные публикации в периодических изданияхстатья

2 Цитирования (Scopus)

Аннотация

A c-interval is the disjoint union of c intervals over N. The c-Interval Multicover problem is the special case of Set Multicover where all sets available for covering are c-intervals. We strengthen known APX-hardness results for c-Interval Multicover, show W[1]-hardness when parameterized by the solution size, and present fixed-parameter algorithms for alternative parameterizations.

Язык оригиналаанглийский
Страницы (с-по)744-749
Число страниц6
ЖурналInformation Processing Letters
Том115
Номер выпуска10
DOI
СостояниеОпубликовано - 1 окт 2015
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «Approximability and parameterized complexity of multicover by c-intervals». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать