{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:59:18Z","timestamp":1780073958922,"version":"3.54.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424703","type":"print"},{"value":"9783540446668","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44666-4_15","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T16:58:07Z","timestamp":1178211487000},"page":"114-126","source":"Crossref","is-referenced-by-count":7,"title":["Minimizing Average Completion of Dedicated Tasks and Interval Graphs"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"15_CR1","series-title":"Lect Notes Comput Sci","volume-title":"FSTTCS 2000","author":"F. Afrati","year":"1974","unstructured":"F. Afrati, E. Bampis, A. Fishkin, K. Jansen, and C. Kenyon. Scheduling to minimize the average completion time of dedicated tasks. In FSTTCS 2000, LNCS, Delhi."},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/jagm.1998.0938","volume":"28","author":"A. Bar-Noy","year":"1998","unstructured":"A. Bar-Noy and G. Kortsarz. The minimum color-sum of bipartite graphs. Journal of Algorithms, 28:339\u2013365, 1998.","journal-title":"Journal of Algorithms"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1998","unstructured":"A. Bar-Noy, M. Bellare, M. M. Halld\u00f3rsson, H. Shachnai, and T. Tamir. On chromatic sums and distributed resource allocation. Information and Computation, 140:183\u2013202, 1998.","journal-title":"Information and Computation"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1109\/87.317982","volume":"2","author":"D. Bullock","year":"1994","unstructured":"D. Bullock and C. Hendrickson. Roadway traffic control software. IEEE Transactions on Control Systems Technology, 2:255\u2013264, 1994.","journal-title":"IEEE Transactions on Control Systems Technology"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, M. M. Halld\u00f3rsson, G. Kortsarz. Tight Bound for the Sum of a Greedy Coloring. Information Processing Letters, 1999.","DOI":"10.1016\/S0020-0190(99)00104-0"},{"issue":"2","key":"15_CR6","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1006\/jagm.2000.1106","volume":"37","author":"A. Bar-Noy","year":"2000","unstructured":"A. Bar-Noy, M. M. Halld\u00f3rsson, G. Kortsarz, H. Shachnai, and R. Salman. Sum Multicoloring of Graphs. Journal of Algorithms, 37(2):422\u2013450, November 2000.","journal-title":"Journal of Algorithms"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/0377-2217(95)00350-9","volume":"90","author":"P. Brucker","year":"1996","unstructured":"P. Brucker and A. Kr\u00e4mer. Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European Journal of Operational Research, 90:214\u2013226, 1996.","journal-title":"European Journal of Operational Research"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/0095-8956(80)90079-9","volume":"29","author":"A. Frank","year":"1980","unstructured":"A. Frank. On Chain and Antichain Families of a Partially Ordered Set. J. Combinatorial Theory, Series B, 29: 176\u2013184, 1980.","journal-title":"J. Combinatorial Theory"},{"key":"15_CR9","volume-title":"M.Sc. Thesis","author":"M. Gonen","year":"2001","unstructured":"M. Gonen, Coloring Problems on Interval Graphs and Trees. M.Sc. Thesis. School of Computer Science, The Open Univ., Israel, 2001."},{"key":"15_CR10","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the Second International Workshop on Approximation algorithms (APPROX\u2019 99)","author":"M. M. Halld\u00f3rsson","year":"1999","unstructured":"M. M. Halld\u00f3rsson and G. Kortsarz. Multicoloring Planar Graphs and Partial k-trees. In Proceedings of the Second International Workshop on Approximation algorithms (APPROX\u2019 99). Lecture Notes in Computer Science Vol. 1671, Springer-Verlag, August 1999."},{"key":"15_CR11","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the Fifth International Computing and Combinatorics Conference (COCOON)","author":"M. M. Halld\u00f3rsson","year":"1999","unstructured":"M. M. Halld\u00f3rsson, G. Kortsarz, A. Proskurowski, R. Salman, H. Shachnai, and J. A. Telle. Multi-Coloring Trees. In Proceedings of the Fifth International Computing and Combinatorics Conference (COCOON), Tokyo, Japan, Lecture Notes in Computer Science Vol. 1627, Springer-Verlag, July 1999."},{"key":"15_CR12","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of the Third Italian Conference on Algorithms and Complexity (CIAC\u2019 97)","author":"K. Jansen","year":"1997","unstructured":"K. Jansen. The Optimum Cost Chromatic Partition Problem. Proc. of the Third Italian Conference on Algorithms and Complexity (CIAC\u2019 97). LNCS 1203, 1997."},{"key":"15_CR13","unstructured":"E. Kubicka. The Chromatic Sum of a Graph. PhD thesis, Western Michigan University, 1989."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/0377-2217(96)00131-2","volume":"94","author":"M. Kubale","year":"1996","unstructured":"M. Kubale. Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors. European Journal of Operational Research 94:242\u2013251, 1996.","journal-title":"European Journal of Operational Research"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/PL00009252","volume":"23","author":"S. Nicoloso","year":"1999","unstructured":"S. Nicoloso, M. Sarrafzadeh and X. Song. On the Sum Coloring Problem on Interval Graphs. Algorithmica, 23:109\u2013126, 1999.","journal-title":"Algorithmica"},{"key":"15_CR16","unstructured":"G. Woeginger. Private communication, 1997."},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"M. Yannakakis and F. Gavril. The maximum k-colorable subgraph problem for chordal graphs. Inform. Proc. Letters, 24:133\u2013137, 1987.","journal-title":"Inform. Proc. Letters"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44666-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T12:46:12Z","timestamp":1550321172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44666-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424703","9783540446668"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44666-4_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}