Standard
Interval scheduling and colorful independent sets. / Van Bevern, René; Mnich, Matthias; Niedermeier, Rolf et al.
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. 2012. p. 247-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Mnich, M, Niedermeier, R & Weller, M 2012,
Interval scheduling and colorful independent sets. in
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7676 LNCS, pp. 247-256, 23rd International Symposium on Algorithms and Computation, ISAAC 2012, Taipei, Taiwan, Province of China,
19.12.2012.
APA
Van Bevern, R., Mnich, M., Niedermeier, R., & Weller, M. (2012).
Interval scheduling and colorful independent sets. In
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings (pp. 247-256). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS).
Vancouver
Van Bevern R, Mnich M, Niedermeier R, Weller M.
Interval scheduling and colorful independent sets. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. 2012. p. 247-256. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Author
Van Bevern, René ; Mnich, Matthias ; Niedermeier, Rolf et al. /
Interval scheduling and colorful independent sets. Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. 2012. pp. 247-256 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{727ff5bac1c3428db752fc4dfa35e19a,
title = "Interval scheduling and colorful independent sets",
abstract = "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.",
author = "{Van Bevern}, Ren{\'e} and Matthias Mnich and Rolf Niedermeier and Mathias Weller",
year = "2012",
month = dec,
day = "31",
language = "English",
isbn = "9783642352607",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "247--256",
booktitle = "Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings",
note = "23rd International Symposium on Algorithms and Computation, ISAAC 2012 ; Conference date: 19-12-2012 Through 21-12-2012",
}
RIS
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 -
