{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:31Z","timestamp":1725861511187},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_16","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T15:50:21Z","timestamp":1468943421000},"page":"194-206","source":"Crossref","is-referenced-by-count":0,"title":["Minimum Cost Homomorphisms with Constrained Costs"],"prefix":"10.1007","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mayssam","family":"Mohammadi Nevisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of $$H$$ -coloring. J. Comb. Theory Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"16_CR2","doi-asserted-by":"crossref","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 19, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"key":"16_CR3","doi-asserted-by":"crossref","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. 154, 881\u2013889 (2006)","journal-title":"Discrete Appl. Math."},{"key":"16_CR4","doi-asserted-by":"crossref","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. J. Algorithms 28, 339\u2013365 (1998)","journal-title":"J. Algorithms"},{"key":"16_CR5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"6","author":"K Supowit","year":"1987","unstructured":"Supowit, K.: Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput.-Aided Des. 6, 93\u201394 (1987)","journal-title":"IEEE Trans. Comput.-Aided Des."},{"key":"16_CR6","doi-asserted-by":"crossref","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 homomorphisms. Eur. J. Comb. 29, 900\u2013911 (2008)","journal-title":"Eur. J. Comb."},{"key":"16_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comp. 28, 57\u2013104 (1998)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"16_CR8","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"16_CR9","doi-asserted-by":"crossref","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 Theory 42, 61\u201380 (2003)","journal-title":"J. Graph Theory"},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"24:1","DOI":"10.1145\/1970398.1970400","volume":"12","author":"A Bulatov","year":"2011","unstructured":"Bulatov, A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic 12, 24:1\u201324:66 (2011)","journal-title":"ACM Trans. Comput. Logic"},{"issue":"4","key":"16_CR11","doi-asserted-by":"crossref","first-page":"1597","DOI":"10.1137\/100783856","volume":"26","author":"P Hell","year":"2012","unstructured":"Hell, P., Rafiey, A.: The dichotomy of minimum cost homomorphism problems for digraphs. SIAM J. Discrete Math. 26(4), 1597\u20131608 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Hell, P., Rafiey, A.: The dichotomy of list homomorphisms for digraphs. In: Proceedings of the Symposium on Discrete Algorithms, SODA 2011, pp. 1703\u20131713 (2011)","DOI":"10.1137\/1.9781611973082.131"},{"key":"16_CR13","unstructured":"Hell, P., Rafiey, A.: Duality for min-max orderings and dichotomy for min cost homomorphisms. arXiv preprint arXiv:0907.3016 (2009)"},{"key":"16_CR14","unstructured":"Hell, P., Rafiey, A.: Minimum cost homomorphism problems to smooth and balanced digraphs. Manuscript (2007)"},{"key":"16_CR15","unstructured":"Takhanov, R.: A dichotomy theorem for the general minimum cost homomorphism problem. In: 27th International Symposium on Theoretical Aspects of Computer Science, vol. 5, pp. 657\u2013668 (2010)"},{"key":"16_CR16","doi-asserted-by":"crossref","first-page":"10:1","DOI":"10.1145\/2450142.2450146","volume":"60","author":"V Kolmogorov","year":"2013","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: The complexity of conservative valued CSPs. J. ACM 60, 10:1\u201310:38 (2013)","journal-title":"J. ACM"},{"key":"16_CR17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0166-218X(97)00027-9","volume":"78","author":"H M\u00fcller","year":"1997","unstructured":"M\u00fcller, H.: Recognizing interval digraphs and interval bigraphs in polynomial. Discrete Appl. Math. 78, 189\u2013205 (1997)","journal-title":"Discrete Appl. Math."},{"key":"16_CR18","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math. 18, 279\u2013292 (1987)","journal-title":"Discrete Appl. Math."},{"key":"16_CR19","doi-asserted-by":"crossref","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. Comb. Theory B 72, 236\u2013250 (1998)","journal-title":"J. Comb. Theory B"},{"key":"16_CR20","doi-asserted-by":"crossref","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 46, 313\u2013327 (2004)","journal-title":"J. Graph Theory"},{"key":"16_CR21","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/S0012-365X(02)00877-4","volume":"265","author":"VE Alekseev","year":"2003","unstructured":"Alekseev, V.E., Lozin, V.V.: Independent sets of maximum weight in (p, q)-colorable graphs. Discrete Math. 265, 351\u2013356 (2003)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T18:44:13Z","timestamp":1498329853000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}