{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:33:02Z","timestamp":1725489182727},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441861"},{"type":"electronic","value":"9783540457534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_13","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T11:37:09Z","timestamp":1187264229000},"page":"135-145","source":"Crossref","is-referenced-by-count":5,"title":["A 27\/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Giaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Janczewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Kubale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Ma\u0142afiejski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1998","unstructured":"Bar-Noy A., Bellare M., Halld\u00f3rsson M.M., Shachnai H., Tamir T.: On chromatic sums and distributed resource allocation. Information and Computation 140 (1998) 183\u2013202","journal-title":"Information and Computation"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/jagm.1998.0938","volume":"28","author":"A. Bar-Noy","year":"1998","unstructured":"Bar-Noy A., Kortsarz G.: Minimum color sum of bipartite graphs. Journal of Algorithms 28 (1998) 339\u2013365","journal-title":"Journal of Algorithms"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"M.E. Dyer","year":"1986","unstructured":"Dyer M.E., Frieze A.M.: Planar 3DM is NP-complete. Journal of Algorithms 7 (1986) 174\u2013184","journal-title":"Journal of Algorithms"},{"key":"13_CR4","unstructured":"Garey M.R., ohnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0020-0190(00)00072-7","volume":"75","author":"K. Giaro","year":"2000","unstructured":"Giaro K., Kubale M.: Edge-chromatic sum of trees and bounded cyclicity graphs. Inf. Proc. Letters 75 (2000) 65\u201369","journal-title":"Inf. Proc. Letters"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Kubicka E., Schwenk A.J.: An introduction to chromatic sums. Proceedings of ACM Computer Science Conference (1989) 39\u201345","DOI":"10.1145\/75427.75430"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Ma\u0142afiejski M.: The complexity of the chromatic sum problem on planar graphs and regular graphs. The First Cologne Twente Workshop on Graphs and Combinatorial Optimization, Cologne (2001), Electronic Notes in Discrete Mathematics 8 (2001)","DOI":"10.1016\/S1571-0653(05)80080-0"},{"key":"13_CR8","unstructured":"Ma\u0142afiejski M.: Scheduling Multiprocessor Tasks to Minimize Mean FlowTime (in Polish), Ph.D. Thesis, Gda\u0144sk University of Technology (2002)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/PL00009252","volume":"23","author":"S. Nicolso","year":"1999","unstructured":"Nicolso S., Sarrafzadeh M., Song X.: On the sum coloring problem on interval graphs. Algorithmica 23 (1999) 109\u2013126","journal-title":"Algorithmica"},{"key":"13_CR10","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, NewJersey (1982)"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/S0097539796303123","volume":"29","author":"T. Szkaliczki","year":"1999","unstructured":"Szkaliczki T.: Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete. SIAM Journal on Computing 29 (1999) 274\u2013287","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:33:07Z","timestamp":1556771587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}