{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:13:24Z","timestamp":1765368804814},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540625599"},{"type":"electronic","value":"9783540680727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62559-3_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:40:50Z","timestamp":1330296050000},"page":"279-292","source":"Crossref","is-referenced-by-count":27,"title":["The Optimal Cost Chromatic Partition problem for trees and interval graphs"],"prefix":"10.1007","author":[{"given":"Leo G.","family":"Kroon","sequence":"first","affiliation":[]},{"given":"Arunabha","family":"Sen","sequence":"additional","affiliation":[]},{"given":"Haiyong","family":"Deng","sequence":"additional","affiliation":[]},{"given":"Asim","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"E.M. Arkin, and E.L. Silverberg. Scheduling jobs with fixed start and finish times. Discrete Applied Mathematics, 18 (1987), 1\u20138.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR2","unstructured":"C. Berge. F\u00e4rbung von Graphen deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther Univ. Halle-Wittenberg. Math.-Natur. Reihe, 114 (1961)."},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"B-18","author":"V. Chvatal","year":"1975","unstructured":"V. Chvatal. On certain polytopes associated with graphs. J. Comb. Theory, B-18 (1975) 138\u2013154.","journal-title":"J. Comb. Theory"},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"S76","DOI":"10.1287\/opre.40.1.S76","volume":"40","author":"V.R. Dondeti","year":"1992","unstructured":"V.R. Dondeti, and H. Emmons. Job scheduling with processors of two types. Operations Research, 40 (1992) S76\u2013S85.","journal-title":"Operations Research"},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/0377-2217(93)90243-G","volume":"70","author":"V.R. Dondeti","year":"1993","unstructured":"V.R. Dondeti, and H. Emmons. Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times. European Journal of Operational Research, 70 (1993) 316\u2013326.","journal-title":"European Journal of Operational Research"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.35.6.849","volume":"6","author":"M. Fischetti","year":"1987","unstructured":"M. Fischetti, S. Martello, and P. Toth. The Fixed Job Schedule Problem with spread time constraints. Operations Research, 6 (1987) 849\u2013858.","journal-title":"Operations Research"},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.37.3.395","volume":"3","author":"M. Fischetti","year":"1989","unstructured":"M. Fischetti, S. Martello, and P. Toth. The Fixed Job Schedule Problem with working time constraints. Operations Research, 3 (1989) 395\u2013403.","journal-title":"Operations Research"},{"key":"23_CR8","doi-asserted-by":"crossref","first-page":"S96","DOI":"10.1287\/opre.40.1.S96","volume":"40","author":"M. Fischetti","year":"1992","unstructured":"M. Fischetti, S. Martello and P. Toth. Approximation algorithms for Fixed Job Schedule Problems. Operations Research, 40 (1992) S96\u2013S108.","journal-title":"Operations Research"},{"key":"23_CR9","volume-title":"Computers and intractability: A guide to the theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, and D.S. Johnson. Computers and intractability: A guide to the theory of NP-Completeness. Freeman, San Fransisco, 1979."},{"key":"23_CR10","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"M.R. Garey, D.S. Johnson, G.L. Miller and C.H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM Journal of Alg. Disc. Meth, 1 (1980) 216\u2013227.","journal-title":"SIAM Journal of Alg. Disc. Meth"},{"key":"23_CR11","first-page":"97","volume":"21","author":"C. Grinstead","year":"1984","unstructured":"C. Grinstead. The perfect graph conjecture for toroidal graphs. Annals of Discrete Mathematics, 21 (1984) 97\u2013101.","journal-title":"Annals of Discrete Mathematics"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lovasz, and A. Schrijver. Geometric algorithms and combinatorial optimization, (1988). Springer Verlag.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0377-2217(91)90320-U","volume":"54","author":"A.W.J. Kolen","year":"1991","unstructured":"A.W.J. Kolen, and L.G. Kroon. On the computational complexity of (maximum) class scheduling. European Journal of Operational Research, 54 (1991), 23\u201338.","journal-title":"European Journal of Operational Research"},{"key":"23_CR14","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/0377-2217(92)90160-B","volume":"63","author":"A.W.J. Kolen","year":"1992","unstructured":"A.W.J. Kolen, and L.G. Kroon. Licence Class Design: complexity and algorithms. European Journal of Operational Research, 63 (1992), 432\u2013444.","journal-title":"European Journal of Operational Research"},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0377-2217(93)90014-E","volume":"64","author":"A.W.J. Kolen","year":"1993","unstructured":"A.W.J. Kolen, and L.G. Kroon. On the computational complexity of (maximum) shift class scheduling. European Journal of Operational Research, 64 (1993), 138\u2013151.","journal-title":"European Journal of Operational Research"},{"key":"23_CR16","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/0377-2217(94)90056-6","volume":"79","author":"A.W.J. Kolen","year":"1994","unstructured":"A.W.J. Kolen, and L.G. Kroon. Analysis of shift class design problems. European Journal of Operational Research, 79 (1994). 417\u2013430.","journal-title":"European Journal of Operational Research"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"E. Kubicka, and A. Schwenk. Introduction to chromatic sums. Proc. ACM Computer Science Conference, (1989).","DOI":"10.1145\/75427.75430"},{"key":"23_CR18","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01580235","volume":"6","author":"M.W. Padberg","year":"1974","unstructured":"M.W. Padberg. Perfect Zero-One matrices. Mathematical Programming, 6 (1974) 180\u2013196.","journal-title":"Mathematical Programming"},{"key":"23_CR19","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/S0095-8956(76)80005-6","volume":"B-21","author":"K.R. Parthasarathy","year":"1976","unstructured":"K.R. Parthasarathy, and G. Ravindra. The Strong Perfect Graph Conjecture is true for K\n1,3-free graphs. J. Comb. Theory, B-21 (1976) 212\u2013223.","journal-title":"J. Comb. Theory"},{"key":"23_CR20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(92)90017-P","volume":"43","author":"A. Sen","year":"1991","unstructured":"A. Sen, H. Deng, and S. Guha. On a graph partition problem with an application to VLSI layout. Information Processing Letters, 43 (1991) 87\u201394.","journal-title":"Information Processing Letters"},{"key":"23_CR21","unstructured":"A. Sen, H. Deng, and A. Roy. On a graph partition problem with application to multiprocessor scheduling. TR-92-020. Department of Computer Science and Engineering, Arizona State University."},{"issue":"1","key":"23_CR22","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"CAD 6","author":"K.J. Supowit","year":"1987","unstructured":"K.J. Supowit. Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. on Computer Aided Design, CAD 6, 1 (1987) 93\u201394.","journal-title":"IEEE Trans. on Computer Aided Design"},{"key":"23_CR23","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4153\/CJM-1973-009-3","volume":"25","author":"A. Tucker","year":"1973","unstructured":"A. Tucker. The Strong Perfect Graph Conjecture for planar graphs. Canad. J. Math, 25 (1973) 103\u2013114.","journal-title":"Canad. J. Math"},{"key":"23_CR24","first-page":"149","volume":"21","author":"A. Tucker","year":"1984","unstructured":"A. Tucker. The validity of the perfect graph conjecture for K\n4-free graphs. Annals of Discrete Mathematics, 21 (1984) 149\u2013157.","journal-title":"Annals of Discrete Mathematics"},{"key":"23_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yanakakis","year":"1987","unstructured":"M. Yanakakis, and F. Gavril. The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters, 24 (1987), 133\u2013137.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62559-3_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:38:36Z","timestamp":1619573916000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62559-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540625599","9783540680727"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-62559-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}