Interval scheduling and colorful independent sets

René Van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

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

Аннотация

The NP-hard Independent Set problem is to determine for a given graph G and an integer κ whether G contains a set of κ pairwise non-adjacent vertices. The problem has numerous applications in scheduling, including resource allocation and steel manufacturing. There, one encounters restricted graph classes such as 2-union graphs, which are edge-wise unions of two interval graphs on the same vertex set, or strip graphs, where additionally one of the two interval graphs is a disjoint union of cliques. We prove NP-hardness of Independent Set on a very restricted subclass of 2-union graphs and identify natural parameterizations to chart the possibilities and limitations of effective polynomial-time preprocessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
Страницы247-256
Число страниц10
СостояниеОпубликовано - 31 дек 2012
Опубликовано для внешнего пользованияДа
Событие23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Китайская Провинция Тайвань
Продолжительность: 19 дек 201221 дек 2012

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7676 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция23rd International Symposium on Algorithms and Computation, ISAAC 2012
СтранаКитайская Провинция Тайвань
ГородTaipei
Период19.12.201221.12.2012

Fingerprint Подробные сведения о темах исследования «Interval scheduling and colorful independent sets». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать