{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:30:23Z","timestamp":1725507023641},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_16","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"182-193","source":"Crossref","is-referenced-by-count":6,"title":["Minimum Cost Homomorphisms to Reflexive Digraphs"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Pavol","family":"Hell","sequence":"additional","affiliation":[]},{"given":"Mehdi","family":"Karimi","sequence":"additional","affiliation":[]},{"given":"Arash","family":"Rafiey","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/S0012-365X(02)00877-4","volume":"265","author":"V.E. Alekseev","year":"2003","unstructured":"Alekseev, V.E., Lozin, V.V.: Independent sets of maximum weight in (p,q)-colorable graphs. Discrete Mathematics\u00a0265, 351\u2013356 (2003)","journal-title":"Discrete Mathematics"},{"key":"16_CR2","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":"16_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(01)00073-5","volume":"244","author":"R.C. Brewster","year":"2002","unstructured":"Brewster, R.C., Hell, P.: Homomorphisms to powers of digraphs. Discrete Mathematics\u00a0244, 31\u201341 (2002)","journal-title":"Discrete Mathematics"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/B:AIRE.0000044479.89075.02","volume":"22","author":"D. Cohen","year":"2004","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: A maximal tractable class of soft constraints. J. Artif. Intell. Res.\u00a022, 1\u201322 (2004)","journal-title":"J. Artif. Intell. Res."},{"key":"16_CR5","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":"16_CR6","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 Theory\u00a042, 61\u201380 (2003)","journal-title":"Graph Theory"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"2458","DOI":"10.1016\/j.dam.2006.02.009","volume":"154","author":"T. Feder","year":"2006","unstructured":"Feder, T., Hell, P., Tucker-Nally, K.: Digraph matrix partitions and trigraph homomorphisms. Discrete Applied Mathematics\u00a0154, 2458\u20132469 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR8","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms to reflexive digraphs (manuscript, 2005)"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/S0895480199383353","volume":"14","author":"T. Feder","year":"2001","unstructured":"Feder, T.: Classification of Homomorphisms to Oriented Cycles and k-Partite Satisfiability. SIAM Journal on Discrete Mathematics\u00a014, 471\u2013480 (2001)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"16_CR10","unstructured":"Gutin, G., Kim, E.J.: Complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops (submitted)"},{"key":"16_CR11","unstructured":"Gutin, G., Kim, E.J.: Introduction to the minimum cost homomorphism problem for directed and undirected graphs. Lecture Notes of the Ramanujan Math. Society (to appear)"},{"key":"16_CR12","unstructured":"Gutin, G., Kim, E.J.: On the complexity of the minimum cost homomorphism problem for reflexive multipartite tournaments (submitted)"},{"key":"16_CR13","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":"16_CR14","doi-asserted-by":"crossref","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs. Discrete Applied Math. (submitted)","DOI":"10.1016\/j.dam.2007.09.023"},{"key":"16_CR15","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs (submitted)"},{"key":"16_CR16","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":"16_CR17","doi-asserted-by":"crossref","unstructured":"Gutin, G., Hell, P., Rafiey, A., Yeo, A.: A dichotomy for minimum cost graph homomorphisms. European J. Combin. (to appear)","DOI":"10.1016\/j.ejc.2007.11.012"},{"key":"16_CR18","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. 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":"16_CR19","series-title":"Lecture Note Series","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1017\/CBO9781107359970.008","volume-title":"Survey in Combinatorics 2003, London Math. Soc.","author":"P. Hell","year":"2003","unstructured":"Hell, P.: Algorithmic aspects of graph homomorphisms. In: Survey in Combinatorics 2003, London Math. Soc. Lecture Note Series, vol.\u00a0307, pp. 239\u2013276. Cambridge University Press, Cambridge (2003)"},{"key":"16_CR20","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":"16_CR21","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":"16_CR22","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":"16_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(96)00099-6","volume":"70","author":"P. Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., Zhu, X.: Complexity of Tree Homomorphisms. Discrete Applied Mathematics\u00a070, 23\u201336 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR24","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":"16_CR25","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":"16_CR26","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030, 1863\u20131920 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"16_CR28","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Combin. Theory, Ser. B\u00a019, 269\u2013271 (1975)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"16_CR29","doi-asserted-by":"publisher","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. Computer-Aided Design\u00a06, 93\u201394 (1987)","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"16_CR30","unstructured":"Wegner, G.: Eigenschaften der nerven homologische-einfactor familien in Rn, Ph.D. Thesis, Universit\u00e4t Gottigen, Gottigen, Germany (1967)"},{"key":"16_CR31","volume-title":"Introduction to Graph Theory","author":"D. West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996)"},{"key":"16_CR32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/0406007","volume":"6","author":"H. Zhou","year":"1993","unstructured":"Zhou, H.: Characterization of the homomorphic preimages of certain oriented cycles. SIAM Journal on Discrete Mathematics\u00a06, 87\u201399 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:21:31Z","timestamp":1619522491000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_16","relation":{},"subject":[]}}