{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T20:48:19Z","timestamp":1673210899592},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,4,4]],"date-time":"2008-04-04T00:00:00Z","timestamp":1207267200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,11]]},"DOI":"10.1007\/s10878-008-9152-2","type":"journal-article","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T17:11:30Z","timestamp":1207242690000},"page":"361-377","source":"Crossref","is-referenced-by-count":5,"title":["Minimum entropy coloring"],"prefix":"10.1007","volume":"16","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,4]]},"reference":[{"issue":"6","key":"9152_CR1","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1016\/S0165-1684(00)00080-3","volume":"80","author":"M Accame","year":"2000","unstructured":"Accame M, De Natale FGB, Granelli F (2000) Efficient labeling procedures for image partition encoding. Signal Process 80(6):1127\u20131131","journal-title":"Signal Process"},{"key":"9152_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal S, Belongie S (2002) On the non-optimality of four color coding of image partitions. In: Proc. IEEE int. conf. image processing","DOI":"10.1109\/ICIP.2002.1040041"},{"issue":"5","key":"9152_CR3","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1109\/18.532875","volume":"42","author":"N Alon","year":"1996","unstructured":"Alon N, Orlitsky A (1996) Source coding and graph entropies. IEEE Trans Inf Theory 42(5):1329\u20131339","journal-title":"IEEE Trans Inf Theory"},{"key":"9152_CR4","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks RL (1941) On colouring the nodes of a network. Proc Camb Philos Soc 37:194\u2013197","journal-title":"Proc Camb Philos Soc"},{"key":"9152_CR5","doi-asserted-by":"crossref","unstructured":"Cardinal J, Fiorini S, Van Assche G (2004) On minimum entropy graph colorings. In: Proc. IEEE int. symposium on information theory, p 43","DOI":"10.1109\/ISIT.2004.1365077"},{"key":"9152_CR6","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal V (1975) On certain polytopes associated with graphs. J Comb Theory Ser B 18:138\u2013154","journal-title":"J Comb Theory Ser B"},{"key":"9152_CR7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1080\/07408179508936730","volume":"27","author":"D Werra de","year":"1995","unstructured":"de Werra D, Glover F, Silver EA (1995) A chromatic scheduling model with costs. IIE Trans 27:181\u2013189","journal-title":"IIE Trans"},{"issue":"1-3","key":"9152_CR8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0012-365X(00)00006-6","volume":"222","author":"D Werra de","year":"2000","unstructured":"de Werra D, Hertz A, Kobler D, Mahadev NVR (2000) Feasible edge colorings of trees with cardinality constraints. Discrete Math 222(1-3):61\u201372","journal-title":"Discrete Math"},{"key":"9152_CR9","series-title":"Graduate Texts in Mathematics","volume-title":"Graph theory","author":"R Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory, 2nd edn. Graduate Texts in Mathematics, vol\u00a0173. Springer, New York","edition":"2"},{"issue":"1","key":"9152_CR10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0012-365X(03)00184-5","volume":"272","author":"P Erd\u00f6s","year":"2003","unstructured":"Erd\u00f6s P, Hedetniemi ST, Laskar RC, Prins GCE (2003) On the equality of the partial Grundy and upper ochromatic numbers of graphs. Discrete Math 272(1):53\u201364. In honor of Frank Harary","journal-title":"Discrete Math"},{"issue":"2","key":"9152_CR11","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U Feige","year":"1998","unstructured":"Feige U, Kilian J (1998) Zero knowledge and the chromatic number. J Comput Syst Sci 57(2):187\u2013199","journal-title":"J Comput Syst Sci"},{"key":"9152_CR12","unstructured":"Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: 1st annual ACM-SIAM symposium on discrete algorithms, pp 434\u2013443"},{"issue":"2","key":"9152_CR13","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"MR Garey","year":"1980","unstructured":"Garey MR, Johnson DS, Miller GL, Papadimitriou CH (1980) The complexity of coloring circular arcs and chords. SIAM J Algebr Discrete Methods 1(2):216\u2013227","journal-title":"SIAM J Algebr Discrete Methods"},{"key":"9152_CR14","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Academic Press, New York"},{"key":"9152_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1993) Geometric algorithms and combinatorial optimization, 2nd edn. Algorithms and Combinatorics, vol\u00a02. Springer, Berlin","edition":"2"},{"key":"9152_CR16","series-title":"Lecture notes in comput. sci.","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/978-3-540-27836-8_62","volume-title":"Automata, languages and programming","author":"E Halperin","year":"2004","unstructured":"Halperin E, Karp RM (2004) The minimum-entropy set cover problem. In: Automata, languages and programming. Lecture notes in comput. sci., vol 3142. Springer, Berlin, pp 733\u2013744"},{"key":"9152_CR17","series-title":"Cambridge Mathematical Library","volume-title":"Inequalities","author":"GH Hardy","year":"1988","unstructured":"Hardy GH, Littlewood JE, P\u00f3lya G (1988) Inequalities. Cambridge Mathematical Library. Cambridge University Press, Cambridge. Reprint of the 1952 edition"},{"key":"9152_CR18","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1006\/jagm.1999.1022","volume":"34","author":"K Jansen","year":"2000","unstructured":"Jansen K (2000) Approximation results for the optimum cost chromatic partition problem. J Algorithms 34:54\u201389","journal-title":"J Algorithms"},{"key":"9152_CR19","volume-title":"Graph coloring problems","author":"TR Jensen","year":"1995","unstructured":"Jensen TR, Toft B (1995) Graph coloring problems. Wiley\u2013Interscience, New York"},{"issue":"3","key":"9152_CR20","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1006\/jcss.1995.1077","volume":"51","author":"J Kahn","year":"1995","unstructured":"Kahn J, Kim JH (1995) Entropy and sorting. J Comput Syst Sci 51(3):390\u2013399","journal-title":"J Comput Syst Sci"},{"key":"9152_CR21","first-page":"411","volume-title":"Transactions of the sixth Prague conference on information theory, statistical decision functions, random processes (Tech Univ., Prague, 1971; dedicated to the memory of Anton\u00edn \u0160pa\u010dek)","author":"J K\u00f6rner","year":"1973","unstructured":"K\u00f6rner J (1973) Coding of an information source having ambiguous alphabet and the entropy of graphs. In: Transactions of the sixth Prague conference on information theory, statistical decision functions, random processes (Tech Univ., Prague, 1971; dedicated to the memory of Anton\u00edn \u0160pa\u010dek). Academia, Prague, pp 411\u2013425"},{"issue":"4","key":"9152_CR22","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D Marx","year":"2005","unstructured":"Marx D (2005) A short proof of the NP-completeness of minimum sum interval coloring. Oper Res Lett 33(4):382\u2013384","journal-title":"Oper Res Lett"},{"key":"9152_CR23","first-page":"562","volume-title":"SODA \u201904: Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms","author":"SV Pemmaraju","year":"2004","unstructured":"Pemmaraju SV, Raman R, Varadarajan K (2004) Buffer minimization using max-coloring. In: SODA \u201904: Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms. Siam, Philadelphia, pp 562\u2013571"},{"key":"9152_CR24","series-title":"Discrete math. optim","first-page":"293","volume-title":"Perfect graphs","author":"G Simonyi","year":"2001","unstructured":"Simonyi G (2001) Perfect graphs and graph entropy. An updated survey. In: Perfect graphs. Discrete math. optim. Wiley, Chichester, pp 293\u2013328"},{"issue":"1","key":"9152_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A Tucker","year":"1980","unstructured":"Tucker A (1980) An efficient test for circular-arc graphs. SIAM J Comput 9(1):1\u201324","journal-title":"SIAM J Comput"},{"issue":"5","key":"9152_CR26","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TIT.1976.1055607","volume":"22","author":"HS Witsenhausen","year":"1976","unstructured":"Witsenhausen HS (1976) The zero-error side information problem and chromatic numbers. IEEE Trans Inf Theory 22(5):592\u2013593","journal-title":"IEEE Trans Inf Theory"},{"key":"9152_CR27","unstructured":"Zhao Q, Effros M (2003) Low complexity code design for lossless and near-lossless side information source codes. In: Proc. IEEE data compression conf."},{"issue":"6","key":"9152_CR28","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3(6):103\u2013128","journal-title":"Theory Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-008-9152-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-008-9152-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-008-9152-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:12Z","timestamp":1559276292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-008-9152-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,4]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["9152"],"URL":"https:\/\/doi.org\/10.1007\/s10878-008-9152-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,4]]}}}