{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T21:09:43Z","timestamp":1771189783592,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,10,2]],"date-time":"2014-10-02T00:00:00Z","timestamp":1412208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10951-014-0398-5","type":"journal-article","created":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T09:58:14Z","timestamp":1412157494000},"page":"449-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Interval scheduling and colorful independent sets"],"prefix":"10.1007","volume":"18","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,2]]},"reference":[{"issue":"4","key":"398_CR1","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., & Zwick, U. (1995). Color-coding. Journal of the ACM, 42(4), 844\u2013856.","journal-title":"Journal of the ACM"},{"issue":"1\u20133","key":"398_CR2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0166-218X(96)00063-7","volume":"71","author":"V Bafna","year":"1996","unstructured":"Bafna, V., Narayanan, B. O., & Ravi, R. (1996). Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Mathematics, 71(1\u20133), 41\u201353.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"398_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M. M., Naor, J., Shachnai, H., & Shapira, I. (2006). Scheduling split intervals. SIAM Journal on Computing, 36(1), 1\u201315.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"398_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H. L., Jansen, B. M. P., & Kratsch, S. (2014). Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1), 277\u2013305.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"398_CR5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: A survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V. B., & Spinrad, J. P. (1999). Graph classes: A survey. Philadelphia: SIAM."},{"key":"398_CR6","unstructured":"Chen, J., Lu, S., Sze, S. H., Zhang, F. (2007). Improved algorithms for path, matching, and packing problems. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 298\u2013307). New York: SIAM."},{"issue":"4","key":"398_CR7","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/moor.1060.0218","volume":"31","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Ostrovsky, R., & Rabani, Y. (2006). Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4), 730\u2013738.","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"398_CR8","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG Corneil","year":"2009","unstructured":"Corneil, D. G., Olariu, S., & Stewart, L. (2009). The LBFS structure and recognition of interval graphs. SIAM Journal on Discrete Mathematics, 23(4), 1905\u20131953.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"398_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. New York: Springer."},{"issue":"4","key":"398_CR10","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1007\/s00224-011-9367-y","volume":"50","author":"MR Fellows","year":"2012","unstructured":"Fellows, M. R., Gaspers, S., & Rosamond, F. A. (2012). Parameterizing by the number of numbers. Theory of Computing Systems, 50(4), 675\u2013693.","journal-title":"Theory of Computing Systems"},{"key":"398_CR11","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer."},{"issue":"3","key":"398_CR12","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D. R., & Gross, O. A. (1965). Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3), 835\u2013855.","journal-title":"Pacific Journal of Mathematics"},{"issue":"3","key":"398_CR13","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237\u2013267.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"398_CR14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., & Niedermeier, R. (2007). Invitation to data reduction and problem kernelization. SIGACT News, 38(1), 31\u201345.","journal-title":"SIGACT News"},{"key":"398_CR15","first-page":"109","volume":"109","author":"A Gy\u00e1rfas","year":"1995","unstructured":"Gy\u00e1rfas, A., & West, D. B. (1995). Multitrack interval graphs. Congressus Numerantium, 109, 109\u2013116.","journal-title":"Congressus Numerantium"},{"key":"398_CR16","unstructured":"Halld\u00f3rsson, M. M., Karlsson, R. K. (2006). Strip graphs: Recognition and scheduling. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science (Vol. 4271, pp. 137\u2013146). Berlin: Springer."},{"issue":"4","key":"398_CR17","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1287\/mnsc.1100.1302","volume":"57","author":"W H\u00f6hn","year":"2011","unstructured":"H\u00f6hn, W., K\u00f6nig, F. G., M\u00f6hring, R. H., & L\u00fcbbecke, M. E. (2011). Integrated sequencing and scheduling in coil coating. Management Science, 57(4), 647\u2013666.","journal-title":"Management Science"},{"issue":"4","key":"398_CR18","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4), 512\u2013530.","journal-title":"Journal of Computer and System Sciences"},{"key":"398_CR19","doi-asserted-by":"crossref","first-page":"4253","DOI":"10.1016\/j.tcs.2010.09.001","volume":"411","author":"M Jiang","year":"2010","unstructured":"Jiang, M. (2010). On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411, 4253\u20134262.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"398_CR20","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/s00453-012-9651-5","volume":"66","author":"M Jiang","year":"2013","unstructured":"Jiang, M. (2013). Recognizing d-interval graphs and d-track interval graphs. Algorithmica, 66(3), 541\u2013563.","journal-title":"Algorithmica"},{"issue":"5","key":"398_CR21","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AW Kolen","year":"2007","unstructured":"Kolen, A. W., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54(5), 530\u2013543.","journal-title":"Naval Research Logistics"},{"key":"398_CR22","doi-asserted-by":"crossref","unstructured":"Koutis, I., Williams, R. (2009). Limits and applications of group algebras for parameterized problems. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science (Vol. 5555, pp. 653\u2013664). New York: Springer.","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"398_CR23","first-page":"58","volume":"113","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S. (2014). Recent developments in kernelization: A survey. Bulletin of the European Association for Theoretical Computer Science, 113, 58\u201397.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"issue":"4","key":"398_CR24","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"HT Kung","year":"1975","unstructured":"Kung, H. T., Luccio, F., & Preparata, F. P. (1975). On finding the maxima of a set of vectors. Journal of the ACM, 22(4), 469\u2013476.","journal-title":"Journal of the ACM"},{"key":"398_CR25","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., & Saurabh, S. (2011). Lower bounds based on the exponential time hypothesis. Bulletin of the European Association for Theoretical Computer Science, 105, 41\u201372.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"398_CR26","unstructured":"Marx, D. (2011). Fixed-parameter tractable scheduling problems. In: Packing and Scheduling Algorithms for Information and Communication Services (Dagstuhl Seminar 11091)."},{"key":"398_CR27","doi-asserted-by":"crossref","unstructured":"Mnich, M., Wiese, A. (2014). Scheduling and fixed-parameter tractability. In: Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science (Vol. 8494, pp. 381\u2013392). Berlin: Springer.","DOI":"10.1007\/978-3-319-07557-0_32"},{"issue":"6","key":"398_CR28","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1524\/itit.2011.0657","volume":"53","author":"RH M\u00f6hring","year":"2011","unstructured":"M\u00f6hring, R. H. (2011). Algorithm engineering and industrial applications. Information Technology, 53(6), 302\u2013311.","journal-title":"Information Technology"},{"issue":"4","key":"398_CR29","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/0196-6774(82)90030-X","volume":"3","author":"K Nakajima","year":"1982","unstructured":"Nakajima, K., & Hakimi, S. L. (1982). Complexity results for scheduling tasks with discrete starting times. Journal of Algorithms, 3(4), 344\u2013361.","journal-title":"Journal of Algorithms"},{"key":"398_CR30","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"4","key":"398_CR31","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02189092","volume":"8","author":"E Scheinerman","year":"1988","unstructured":"Scheinerman, E. (1988). Random interval graphs. Combinatorica, 8(4), 357\u2013371.","journal-title":"Combinatorica"},{"key":"398_CR32","volume-title":"Combinatorial optimization: Polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial optimization: Polyhedra and efficiency (Vol. A). Berlin: Springer."},{"issue":"5","key":"398_CR33","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"FCR Spieksma","year":"1999","unstructured":"Spieksma, F. C. R. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2(5), 215\u2013227.","journal-title":"Journal of Scheduling"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-014-0398-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-014-0398-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-014-0398-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:39:50Z","timestamp":1559468390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-014-0398-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,2]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["398"],"URL":"https:\/\/doi.org\/10.1007\/s10951-014-0398-5","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,2]]}}}