Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Interval scheduling and colorful independent sets. / Van Bevern, René; Mnich, Matthias; Niedermeier, Rolf и др.
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. 2012. стр. 247-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 7676 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Interval scheduling and colorful independent sets
AU - Van Bevern, René
AU - Mnich, Matthias
AU - Niedermeier, Rolf
AU - Weller, Mathias
PY - 2012/12/31
Y1 - 2012/12/31
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84871565797&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84871565797
SN - 9783642352607
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 247
EP - 256
BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012
Y2 - 19 December 2012 through 21 December 2012
ER -
ID: 22341067