{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:33:41Z","timestamp":1767339221909,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_51","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"587-598","source":"Crossref","is-referenced-by-count":10,"title":["Approximation of Minimum Cost Homomorphisms"],"prefix":"10.1007","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]},{"given":"Mayssam Mohammadi","family":"Nevisi","sequence":"additional","affiliation":[]},{"given":"Arash","family":"Rafiey","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"51_CR1","unstructured":"Aggarwal, G., Feder, T., Motwani, R., Zhu, A.: Channel assignment in wireless networks and classiffcation of minimum graph homomorphisms. Electronic Colloq. on Comput. Complexity (ECCC) TR06-040 (2006)"},{"key":"51_CR2","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T. Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List Homomorphism to reflexive graphs. J. Combin. Theory B\u00a072, 236\u2013250 (1998)","journal-title":"J. Combin. Theory B"},{"key":"51_CR3","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica\u00a019, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"key":"51_CR4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T. Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Th.\u00a042, 61\u201380 (2003)","journal-title":"J. Graph Th."},{"issue":"6","key":"51_CR5","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1016\/j.dam.2011.04.016","volume":"160","author":"T. Feder","year":"2012","unstructured":"Feder, T., Hell, P., Huang, J., Rafiey, A.: Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discrete Appl. Math.\u00a0160(6), 697\u2013707 (2012)","journal-title":"Discrete Appl. Math."},{"key":"51_CR6","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/080738866","volume":"24","author":"T. Feder","year":"2010","unstructured":"Feder, T., Hell, P., Jonsson, P., Krokhin, A., Nordh, G.: Retractions to pseudo-forests. SIAM J. on Discrete Math.\u00a024, 101\u2013112 (2010)","journal-title":"SIAM J. on Discrete Math."},{"key":"51_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-78773-0_16","volume-title":"LATIN 2008: Theoretical Informatics","author":"A. Gupta","year":"2008","unstructured":"Gupta, A., Hell, P., Karimi, M., Rafiey, A.: Minimum Cost Homomorphisms to Reflexive Digraphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 182\u2013193. Springer, Heidelberg (2008)"},{"key":"51_CR8","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.dam.2005.06.012","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A., Tso, M.: Level of repair analysis and minimum cost homomorphisms of graphs. Discrete Appl. Math.\u00a0154, 881\u2013889 (2006)","journal-title":"Discrete Appl. Math."},{"key":"51_CR9","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.ejc.2007.11.012","volume":"29","author":"G. Gutin","year":"2008","unstructured":"Gutin, G., Hell, P., Rafiey, A., Yeo, A.: A dichotomy for minimum cost graph homomorphisms. European J. Combin.\u00a029, 900\u2013911 (2008)","journal-title":"European J. Combin."},{"key":"51_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-44666-4_15","volume-title":"Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques","author":"M.M. Halld\u00f3rsson","year":"2001","unstructured":"Halld\u00f3rsson, M.M., Kortsarz, G., Shachnai, H.: Minimizing Average Completion of Dedicated Tasks and Interval Graphs. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol.\u00a02129, pp. 114\u2013126. Springer, Heidelberg (2001)"},{"key":"51_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20006","volume":"46","author":"P. Hell","year":"2004","unstructured":"Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. J. Graph Theory\u00a046, 313\u2013327 (2004)","journal-title":"J. Graph Theory"},{"key":"51_CR12","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and homomorphisms. Oxford University Press (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Hell, P., Rafiey, A.: The dichotomy of list homomorphisms for digraphs. In: SODA 2011 (2011)","DOI":"10.1137\/1.9781611973082.131"},{"key":"51_CR14","unstructured":"Hell, P., Rafiey, A.: Duality for min-max orderings and dichotomy for minimum cost homomorphisms, arXiv:0907.3016v1 [cs.DM]"},{"key":"51_CR15","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. J. Algorithms\u00a034, 54\u201389 (2000)","journal-title":"J. Algorithms"},{"key":"51_CR16","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1002\/(SICI)1097-0118(199912)32:4<354::AID-JGT4>3.0.CO;2-B","volume":"32","author":"T. Jiang","year":"1999","unstructured":"Jiang, T., West, D.B.: Coloring of trees with minimum sum of colors. J. Graph Theory\u00a032, 354\u2013358 (1999)","journal-title":"J. Graph Theory"},{"key":"51_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-62559-3_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L.G. Kroon","year":"1997","unstructured":"Kroon, L.G., Sen, A., Deng, H., Roy, A.: The Optimal Cost Chromatic Partition Problem for Trees and Interval Graphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 279\u2013292. Springer, Heidelberg (1997)"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Larose, B., Lemaitre, A.: List-homomorphism problems on graphs and arc consistency (2012) (manuscript)","DOI":"10.1109\/ISMVL.2012.23"},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica\u00a037, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"key":"51_CR20","doi-asserted-by":"crossref","unstructured":"Mastrolilli, M., Rafiey, A.: On the approximation of minimum cost homomorphism to bipartite graphs. Discrete Applied Mathematics (June 22, 2011) (in press), \n                  \n                    http:\/\/dx.doi.org\/10.1016\/j.dam.2011.05.002","DOI":"10.1016\/j.dam.2011.05.002"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:55:01Z","timestamp":1620129301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}