{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:59:51Z","timestamp":1725515991563},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540688655"},{"type":"electronic","value":"9783540688808"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68880-8_22","type":"book-chapter","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T06:37:59Z","timestamp":1217486279000},"page":"224-234","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Cost Homomorphism Dichotomy for Oriented Cycles"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arash","family":"Rafiey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2000","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer, London (2000)"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/S0895480199383353","volume":"14","author":"T. Feder","year":"2001","unstructured":"Feder, T.: Homomorphisms to oriented cycles and k-partite satisfiability. SIAM J. Discrete Math.\u00a014, 471\u2013480 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"22_CR3","unstructured":"Feder, T., Hell, P., Rafiey, A.: List homomorphism to balanced digraphs (submitted)"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hell, P., Karimi, M., Rafiey, A.: Minimum cost homomorphisms to reflexive digraphs. In: LATIN 2008 (to appear, 2008)","DOI":"10.1007\/978-3-540-78773-0_16"},{"key":"22_CR5","unstructured":"Gutin, G., Hell, P., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs. Europ. J. Combin. (to appear)"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.dam.2005.11.006","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost and List Homomorphisms to Semicomplete Digraphs. Discrete Appl. Math.\u00a0154, 890\u2013897 (2006)","journal-title":"Discrete Appl. Math."},{"key":"22_CR7","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs. Discrete Applied Math. (to apear)"},{"key":"22_CR8","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs (submitted)"},{"key":"22_CR9","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); Preliminary version appeared. In: Megiddo, N., Xu, Y., Zhu, B. (eds.): AAIM 2005. LNCS, vol.\u00a03521, pp. 427\u2013439. Springer, Heidelberg (2005)","journal-title":"Discrete Appl. Math."},{"key":"22_CR10","unstructured":"Gutjahr, W.: Graph Colourings, PhD thesis, Free University, Berlin (1991)"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF02122553","volume":"8","author":"R. H\u00e4ggkvist","year":"1988","unstructured":"H\u00e4ggkvist, R., Hell, P., Miller, D.J., Neumann-Lara, V.: On multiplicative graphs and the product conjecture. Combinatorica\u00a08, 63\u201374 (1988)","journal-title":"Combinatorica"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-44666-4_15","volume-title":"Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques","author":"M.M. Halldorsson","year":"2001","unstructured":"Halldorsson, 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":"22_CR13","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":"22_CR14","doi-asserted-by":"publisher","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-colouring. J. Combin. Theory B\u00a048, 92\u2013110 (1990)","journal-title":"J. Combin. Theory B"},{"key":"22_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1137\/S0895480192239992","volume":"8","author":"P. Hell","year":"1995","unstructured":"Hell, P., Zhu, X.: The existence of homomorphisms to oriented cycles. SIAM J. Discrete Math.\u00a08, 208\u2013222 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"22_CR17","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":"22_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0166-218X(92)90262-9","volume":"36","author":"X. Zhu","year":"1992","unstructured":"Zhu, X.: A simple proof of the multipilicatively of directed cycles of prime power length. Discrete Appl. Math.\u00a036, 333\u2013345 (1992)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68880-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:17:03Z","timestamp":1620015423000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68880-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688655","9783540688808"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68880-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}