{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:28:50Z","timestamp":1672568930575},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2012,7,27]],"date-time":"2012-07-27T00:00:00Z","timestamp":1343347200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00236-012-0164-0","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:58:42Z","timestamp":1343314722000},"page":"381-394","source":"Crossref","is-referenced-by-count":8,"title":["Finding vertex-surjective graph homomorphisms"],"prefix":"10.1007","volume":"49","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[]},{"given":"Bernard","family":"Lidick\u00fd","sequence":"additional","affiliation":[]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,7,27]]},"reference":[{"key":"164_CR1","doi-asserted-by":"crossref","unstructured":"Adiga, A., Chitnis, R., Saurabh, S.: Parameterized algorithms for boxicity. In: Proceedings of ISAAC 2010, LNCS 6506, pp. 366\u2013377 (2010)","DOI":"10.1007\/978-3-642-17517-6_33"},{"key":"164_CR2","doi-asserted-by":"crossref","first-page":"1680","DOI":"10.1016\/j.dam.2012.03.029","volume":"160","author":"M. Bodirsky","year":"2012","unstructured":"Bodirsky M., K\u00e1ra J., Martin B.: The complexity of surjective homomorphism problems\u2014a survey. Discrete Appl. Math. 160, 1680\u20131690 (2012)","journal-title":"Discrete Appl. Math."},{"key":"164_CR3","doi-asserted-by":"crossref","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Proceedings of MFCS 2006, LNCS 4162, pp. 238\u2013249 (2006)","DOI":"10.1007\/11821069_21"},{"key":"164_CR4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle B., Olariu S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"164_CR5","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Proceedings of CP 2002, LNCS 2470, pp. 223\u2013254 (2006)","DOI":"10.1007\/3-540-46135-3_21"},{"key":"164_CR6","doi-asserted-by":"crossref","unstructured":"Enciso, R., Fellows, M.R., Guo, J., Kanj, I.A., Rosamond, F.A., Such\u00fd, O.: What makes equitable connected partition easy, In: Proceedings of IWPEC 2009, LNCS 5917, pp. 122\u2013133 (2009)","DOI":"10.1007\/978-3-642-11269-0_10"},{"key":"164_CR7","doi-asserted-by":"crossref","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 pseudoforests. SIAM J. Discrete Math. 24, 101\u2013112 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"164_CR8","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of ISAAC 2008, LNCS 5369, pp. 294\u2013305 (2008)","DOI":"10.1007\/978-3-540-92182-0_28"},{"key":"164_CR9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.cosrev.2008.06.001","volume":"2","author":"J. Fiala","year":"2008","unstructured":"Fiala J., Kratochv\u00edl J.: Locally constrained graph homomorphisms\u2014structure, complexity, and applications. Comput. Sci. Rev. 2, 97\u2013111 (2008)","journal-title":"Comput. Sci. Rev."},{"key":"164_CR10","doi-asserted-by":"crossref","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J. Fiala","year":"2011","unstructured":"Fiala J., Golovach P.A., Kratochv\u00edl J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412, 2513\u20132523 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"164_CR11","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"J. Fiala","year":"2005","unstructured":"Fiala J., Paulusma D.: A complete complexity classification of the role assignment problem. Theor. Comput. Sci. 349, 67\u201381 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"164_CR12","volume-title":"Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series","author":"J. Flum","year":"2006","unstructured":"Flum J., Grohe M.: Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"164_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A. Frank","year":"1987","unstructured":"Frank A., Tardos \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"164_CR14","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.R.: Computers and Intractability. Freeman, New York (1979)"},{"key":"164_CR15","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Computing vertex-surjective homomorphisms to partially reflexive trees. Proceedings of CSR 2011, LNCS 6651, pp. 261\u2013274 (2011)","DOI":"10.1007\/978-3-642-20712-9_20"},{"key":"164_CR16","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J ACM 54(1), Art no 1 (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"164_CR17","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-colouring. J. Comb. Theory Ser. B 48, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"164_CR18","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":"164_CR19","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra Jr.","year":"1983","unstructured":"Lenstra H.W. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"164_CR20","doi-asserted-by":"crossref","unstructured":"Martin, B., Paulusma, D.: The computational complexity of disconnected cut and 2K2-Partition. In: Proceedings of CP 2011, LNCS 6876, pp. 561\u2013575 (2011)","DOI":"10.1007\/978-3-642-23786-7_43"},{"key":"164_CR21","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1137\/S0097539701383522","volume":"32","author":"N. Vikas","year":"2002","unstructured":"Vikas N.: Computational complexity of compaction to reflexive cycles. SIAM J. Comput. 32, 253\u2013280 (2002)","journal-title":"SIAM J. Comput."},{"key":"164_CR22","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1137\/S0097539701397801","volume":"33","author":"N. Vikas","year":"2004","unstructured":"Vikas N.: Compaction, retraction, and constraint satisfaction. SIAM J. Comput. 33, 761\u2013782 (2004)","journal-title":"SIAM J. Comput."},{"key":"164_CR23","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.jcss.2004.07.003","volume":"71","author":"N. Vikas","year":"2005","unstructured":"Vikas N.: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results. J. Comput. Syst. Sci. 71, 406\u2013439 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"164_CR24","doi-asserted-by":"crossref","unstructured":"Vikas, N.: Algorithms for partition of some class of graphs under compaction. In: Proceedings of COCOON 2011, LNCS 6842, pp. 319\u2013330 (2011)","DOI":"10.1007\/978-3-642-22685-4_29"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0164-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-012-0164-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0164-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T18:52:27Z","timestamp":1562007147000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-012-0164-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,27]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["164"],"URL":"https:\/\/doi.org\/10.1007\/s00236-012-0164-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,27]]}}}