{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T20:25:25Z","timestamp":1768422325312,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540309352","type":"print"},{"value":"9783540324263","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_82","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"819-828","source":"Crossref","is-referenced-by-count":8,"title":["Minimum Entropy Coloring"],"prefix":"10.1007","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","reference":[{"issue":"6","key":"82_CR1","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1016\/S0165-1684(00)00080-3","volume":"80","author":"M. Accame","year":"2000","unstructured":"Accame, M., De Natale, F.G.B., Granelli, F.: Efficient labeling procedures for image partition encoding. Signal Processing\u00a080(6), 1127\u20131131 (2000)","journal-title":"Signal Processing"},{"key":"82_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, S., Belongie, S.: On the non-optimality of four color coding of image partitions. In: Proc. IEEE Int. Conf. Image Processing (2002)","DOI":"10.1109\/ICIP.2002.1040041"},{"issue":"5","key":"82_CR3","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1109\/18.532875","volume":"42","author":"N. Alon","year":"1996","unstructured":"Alon, N., Orlitsky, A.: Source coding and graph entropies. IEEE Trans. Inform. Theory\u00a042(5), 1329\u20131339 (1996)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"82_CR4","first-page":"422","volume-title":"36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995)","author":"M. Bellare","year":"1995","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability\u2014towards tight results. In: 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995), pp. 422\u2013431. IEEE Comput. Soc. Press, Los Alamitos (1995)"},{"key":"82_CR5","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proc. Cambridge Philos. Soc.\u00a037, 194\u2013197 (1941)","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"82_CR6","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Fiorini, S., Van Assche, G.: On minimum entropy graph colorings. In: Proc. IEEE Int. Symposium on Information Theory, p. 43 (2004)","DOI":"10.1109\/ISIT.2004.1365077"},{"key":"82_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1080\/07408179508936730","volume":"27","author":"D. Werra de","year":"1995","unstructured":"de Werra, D., Glover, F., Silver, E.A.: A chromatic scheduling model with costs. IIE Trans.\u00a027, 181\u2013189 (1995)","journal-title":"IIE Trans."},{"issue":"1-3","key":"82_CR8","doi-asserted-by":"publisher","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, N.V.R.: Feasible edge colorings of trees with cardinality constraints. Discrete Math.\u00a0222(1-3), 61\u201372 (2000)","journal-title":"Discrete Math."},{"issue":"2","key":"82_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"82_CR10","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"82_CR11","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, London (2004)"},{"key":"82_CR12","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.: Geometric algorithms and combinatorial optimization, 2nd edn. Algorithms and Combinatorics, vol.\u00a02. Springer, Berlin (1993)","edition":"2"},{"key":"82_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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, R.M.: The minimum-entropy set cover problem. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 733\u2013744. Springer, Heidelberg (2004)"},{"key":"82_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jagm.1999.1022","volume":"34","author":"K. Jansen","year":"2000","unstructured":"Jansen, K.: Approximation results for the optimum cost chromatic partition problem. Journal of Algorithms\u00a034, 54\u201389 (2000)","journal-title":"Journal of Algorithms"},{"key":"82_CR15","volume-title":"Graph Coloring Problems","author":"T.R. Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience, Hoboken (1995)"},{"issue":"3","key":"82_CR16","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1006\/jcss.1995.1077","volume":"51","author":"J. Kahn","year":"1995","unstructured":"Kahn, J., Kim, J.H.: Entropy and sorting. J. Comput. Syst. Sci.\u00a051(3), 390\u2013399 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"82_CR17","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D. Marx","year":"2005","unstructured":"Marx, D.: A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett.\u00a033(4), 382\u2013384 (2005)","journal-title":"Oper. Res. Lett."},{"key":"82_CR18","series-title":"Wiley-Intersci. Ser. Discrete Math. Optim.","first-page":"293","volume-title":"Perfect graphs","author":"G. Simonyi","year":"2001","unstructured":"Simonyi, G.: Perfect graphs and graph entropy. An updated survey. In: Perfect graphs. Wiley-Intersci. Ser. Discrete Math. Optim., pp. 293\u2013328. Wiley, Chichester (2001)"},{"issue":"1","key":"82_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"Tucker, A.: An efficient test for circular-arc graphs. SIAM J. Comput.\u00a09(1), 1\u201324 (1980)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"82_CR20","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TIT.1976.1055607","volume":"22","author":"H.S. Witsenhausen","year":"1976","unstructured":"Witsenhausen, H.S.: The zero-error side information problem and chromatic numbers. IEEE Trans. Inform. Theory\u00a022(5), 592\u2013593 (1976)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"82_CR21","unstructured":"Zhao, Q., Effros, M.: Low complexity code design for lossless and near-lossless side information source codes. In: Proc. IEEE Data Compression Conf. (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_82.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:03:11Z","timestamp":1619506991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11602613_82","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}