{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:57Z","timestamp":1759638717207},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_18","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"176-187","source":"Crossref","is-referenced-by-count":15,"title":["Approximation Algorithms for Graph Homomorphism Problems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Langberg","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Aggarwal, G., Feder, T., Motwani, R., Zhu, A.: Channel assignment in wireless networks and classification of minimum graph homomorphism. In: ECCC: TR06-040 (2006)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings, 44th FOCS, pp. 298\u2013307 (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S. Arora","year":"1999","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci.\u00a058, 193\u2013210 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L. Babai","year":"1980","unstructured":"Babai, L., Erd\u00f6s, P., Selkow, S.: Random graph isomorphism. SICOMP\u00a09, 628\u2013635 (1980)","journal-title":"SICOMP"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences\u00a060, 564\u2013574 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Wirth, A.: Maximizing quadratic programs: Extending Grothendieck\u2019s inequality. In: Proceedings, 45th FOCS, pp. 54\u201360 (2004)","DOI":"10.1109\/FOCS.2004.39"},{"key":"18_CR7","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. Journal of Artificial Intelligence Research\u00a022, 1\u201322 (2004)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/jagm.2000.1142","volume":"39","author":"C. Cooper","year":"2001","unstructured":"Cooper, C., Dyer, M., Frieze, A.: On Markov chains for randomly H-coloring a graph. Journal of Algorithms\u00a039, 117\u2013134 (2001)","journal-title":"Journal of Algorithms"},{"key":"18_CR9","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SICOMP\u00a023, 864\u2013894 (1994)","journal-title":"SICOMP"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Feige, U., Hajiaghayi, M.T., Salavatipour, M.: Combination can be hard: Approximability of the unique coverage problem. In: Proceedings, 17th SODA, pp. 162\u2013171 (2006)","DOI":"10.1145\/1109557.1109577"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-36379-3_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Serna, M.J., Thilikos, D.M.: The complexity of restrictive H-coloring. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 126\u2013137. Springer, Heidelberg (2002)"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1002\/rsa.20036","volume":"25","author":"M.E. Dyer","year":"2004","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Structures and Algorithms\u00a025, 346\u2013352 (2004)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR13","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 homomorphisms to reflexive graphs. Journal of Combinatorial Theory, Series B\u00a072, 236\u2013250 (1998)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings, 34th STOC, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-48224-5_18","volume-title":"Automata, Languages and Programming","author":"U. Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: The RPR2\u0302 rounding technique for semidefinite programs. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 213\u2013224. Springer, Heidelberg (2001)"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0020-0190(00)00065-X","volume":"75","author":"A. Freund","year":"2000","unstructured":"Freund, A., Karloff, H.: A lower bound of \n                    \n                      \n                    \n                    $8\/(7+\\frac{1}{k-1})$\n                   on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut. Information Processing Letters\u00a075, 43\u201350 (2000)","journal-title":"Information Processing Letters"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms\u00a010, 5\u201342 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"18_CR19","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 Applied Mathematics\u00a0154, 881\u2013889 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"18_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-coloring. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR21","doi-asserted-by":"publisher","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 Univ. Press, Oxford (2004)"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Kann, V.: On the approximability of the maximum common subgraph problem. In: Proceedings, 9th STACS, pp. 377\u2013388 (1992)","DOI":"10.1007\/3-540-55210-3_198"},{"key":"18_CR23","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"D. Karger","year":"2004","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. M. of OR\u00a029, 436\u2013461 (2004)","journal-title":"M. of OR"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J. Kleinberg","year":"2002","unstructured":"Kleinberg, J., Tardos, \u00c9.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. Journal of the ACM\u00a049, 616\u2013639 (2002)","journal-title":"Journal of the ACM"},{"key":"18_CR25","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok\u00a048, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:13:35Z","timestamp":1619507615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11830924_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}