{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T05:25:01Z","timestamp":1749101101561},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540003311"},{"type":"electronic","value":"9783540363798"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"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":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36379-3_11","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:05Z","timestamp":1269882725000},"page":"114-125","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Weighted Node Coloring: When Stable Sets Are Expensive"],"prefix":"10.1007","author":[{"given":"Marc","family":"Demange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. de","family":"Werra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,28]]},"reference":[{"key":"11_CR1","unstructured":"Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Time slot scheduling of compatible jobs. Cahier du LAMSADE 182, LAMSADE, Universit Paris-Dauphine (2001) Available on www address: \n                  http:\/\/www.lamsade.dauphine.fr\/cahdoc.html#cahiers\n                  \n                ."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"C.N. Potts","year":"2000","unstructured":"Potts, C.N., Kovalyov, M.Y.: Scheduling with batching: a review. European J. Oper. Res. 120 (2000) 228\u2013249","journal-title":"European J. Oper. Res."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/1099-1425(200101\/02)4:1<25::AID-JOS58>3.0.CO;2-7","volume":"4","author":"C.N. Potts","year":"2001","unstructured":"Potts, C.N., Strusevich, V.A., Tautenhahn, T.: Scheduling batches with simultaneous job processing for two-machine shop problems. J. of Scheduling 4 (2001) 25\u201351","journal-title":"J. of Scheduling"},{"key":"11_CR4","unstructured":"Boudhar, M., Finke, G.: Scheduling on a batch machine with job compatibilities. JORBEL (2001) To appear."},{"key":"11_CR5","unstructured":"Berge, C.: Graphs and hypergraphs. North Holland, Amsterdam (1973)"},{"key":"11_CR6","first-page":"191","volume":"7","author":"D. Werra de","year":"1990","unstructured":"de Werra, D.: Heuristics for graph coloring. Computing 7 (1990) 191\u2013208","journal-title":"Computing"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H.U. Simon","year":"1990","unstructured":"Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Disc. Math. 3 (1990) 294\u2013310","journal-title":"SIAM J. Disc. Math."},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9 (1974) 256\u2013278","journal-title":"J. Comput. System Sci."},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/A:1008764212265","volume":"16","author":"L. Alfandari","year":"2000","unstructured":"Alfandari, L., Paschos, V.T.: Master-slave strategy and polynomial approximation. Comput. Opti. Appl. 16 (2000) 231\u2013245","journal-title":"Comput. Opti. Appl."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"B.B. Boppana","year":"1992","unstructured":"Boppana, B.B., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT 32 (1992) 180\u2013196","journal-title":"BIT"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Jansen, K., Woeginger, G.J.: Scheduling with incompatible jobs. Discrete Appl. Math. 55 (1994) 219\u2013232","journal-title":"Discrete Appl. Math."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01858447","volume":"12","author":"D. Werra de","year":"1996","unstructured":"de Werra, D., Erschler, J.: Open shop scheduling with some additional constraints. Graphs and Combinatorics 12 (1996) 81\u201393","journal-title":"Graphs and Combinatorics"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0167-6377(85)90042-2","volume":"4","author":"F. Rendl","year":"1985","unstructured":"Rendl, F.: On the complexity of decomposing matrices arising in satellite communication. Oper. Res. Lett. 4 (1985) 5\u20138","journal-title":"Oper. Res. Lett."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D. K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: ber graphen und iher anwendung auf determinantentheorie und mengenlehre. Math. Ann. 77 (1916) 453\u2013465","journal-title":"Math. Ann."},{"key":"11_CR15","unstructured":"Chvtal, V.: Perfectly ordered graphs. In Berge, C., Chvtal, V., eds.: Topics on Perfect Graphs. (Volume 21 of Annals of Discrete Math.) 253\u2013277"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K. Jansen","year":"1997","unstructured":"Jansen, K., Scheffler, P.: Generalized coloring for tree-like graphs. Discrete Appl. Math. 75 (1997) 135\u2013155","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36379-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T22:12:32Z","timestamp":1578521552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36379-3_11"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540003311","9783540363798"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-36379-3_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"28 February 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}