{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:53:54Z","timestamp":1725742434369},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401633"},{"type":"electronic","value":"9783642401640"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40164-0_14","type":"book-chapter","created":{"date-parts":[[2013,7,21]],"date-time":"2013-07-21T21:01:30Z","timestamp":1374440490000},"page":"121-132","source":"Crossref","is-referenced-by-count":1,"title":["Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree"],"prefix":"10.1007","author":[{"given":"Steven","family":"Chaplick","sequence":"first","affiliation":[]},{"given":"Ji\u0159\u00ed","family":"Fiala","sequence":"additional","affiliation":[]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Tesa\u0159","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proc. STOC 1980, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0095-8956(81)90062-9","volume":"30","author":"D. Angluin","year":"1981","unstructured":"Angluin, D., Gardiner, A.: Finite common coverings of pairs of regular graphs. J. Comb. Theory Ser. B\u00a030, 184\u2013187 (1981)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Biggs, N.: Algebraic Graph Theory. Cambridge University Press (1974)","DOI":"10.1017\/CBO9780511608704"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1112\/jlms\/s2-26.2.193","volume":"26","author":"N. Biggs","year":"1982","unstructured":"Biggs, N.: Constructing 5-arc transitive cubic graphs. J. London Math. Society II\u00a026, 193\u2013200 (1982)","journal-title":"J. London Math. Society II"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0743-7315(89)90048-8","volume":"6","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: The classification of coverings of processor networks. J. Par. Distrib. Comp.\u00a06, 166\u2013182 (1989)","journal-title":"J. Par. Distrib. Comp."},{"issue":"6","key":"14_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comp.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comp."},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-540-30203-2_18","volume-title":"Graph Transformations","author":"J. Chalopin","year":"2004","unstructured":"Chalopin, J., M\u00e9tivier, Y., Zielonka, W.: Election, naming and cellular edge local computations. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol.\u00a03256, pp. 242\u2013256. Springer, Heidelberg (2004)"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 310\u2013326. Springer, Heidelberg (2002)"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0165-4896(91)90080-B","volume":"21","author":"M.G. Everett","year":"1991","unstructured":"Everett, M.G., Borgatti, S.: Role coloring a graph. Mathematical Social Sciences\u00a021, 183\u2013188 (1991)","journal-title":"Mathematical Social Sciences"},{"key":"14_CR10","doi-asserted-by":"publisher","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 \u2013 Structure, complexity, and applications. Comp. Sci. Review\u00a02, 97\u2013111 (2008)","journal-title":"Comp. Sci. Review"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.7151\/dmgt.1159","volume":"22","author":"J. Fiala","year":"2002","unstructured":"Fiala, J., Kratochv\u00edl, J.: Partial covers of graphs. Disc. Math. Graph Theory\u00a022, 89\u201399 (2002)","journal-title":"Disc. Math. Graph Theory"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Kratochv\u00edl, J., Kloks, T.: Fixed-parameter complexity of \u03bb-labelings. Discr. Appl. Math.\u00a0113, 59\u201372 (2001)","journal-title":"Discr. Appl. Math."},{"key":"14_CR13","doi-asserted-by":"publisher","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. Comp. Sci.\u00a0349, 67\u201381 (2005)","journal-title":"Theor. Comp. Sci."},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1007\/s00224-009-9200-z","volume":"46","author":"J. Fiala","year":"2010","unstructured":"Fiala, J., Paulusma, D.: Comparing universal covers in polynomial time. Theory Comp. Syst.\u00a046, 620\u2013635 (2010)","journal-title":"Theory Comp. Syst."},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0012-365X(00)00009-1","volume":"222","author":"A. Galluccio","year":"2000","unstructured":"Galluccio, A., Hell, P., Ne\u0161et\u0159il, J.: The complexity of H-colouring of bounded degree graphs. Discr. Math.\u00a0222, 101\u2013109 (2000)","journal-title":"Discr. Math."},{"key":"14_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H.\u00a0Freeman & Co., New York (1979)"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM\u00a054 (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-40064-8_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Gurski","year":"2000","unstructured":"Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without K\n                \n                  n,n\n                . In: Brandes, U., Wagner, D. (eds.) WG 2000. LNCS, vol.\u00a01928, pp. 196\u2013205. Springer, Heidelberg (2000)"},{"key":"14_CR19","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. Comb. Theory Ser. B\u00a048, 92\u2013110 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.jda.2011.12.004","volume":"14","author":"P. Heggernes","year":"2012","unstructured":"Heggernes, P., van \u2019t Hof, P., Paulusma, D.: Computing role assignments of proper interval graphs in polynomial time. J. Discr. Alg.\u00a014, 173\u2013188 (2012)","journal-title":"J. Discr. Alg."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol.\u00a0842. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"14_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BFb0017162","volume-title":"Mathematical Foundations of Computer Science 1988","author":"J. Kratochv\u00edl","year":"1988","unstructured":"Kratochv\u00edl, J., K\u0159iv\u00e1nek, M.: On the computational complexity of codes in graphs. In: Koubek, V., Janiga, L., Chytil, M.P. (eds.) MFCS 1988. LNCS, vol.\u00a0324, pp. 396\u2013404. Springer, Heidelberg (1988)"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1996.1743","volume":"71","author":"J. Kratochv\u00edl","year":"1997","unstructured":"Kratochv\u00edl, J., Proskurowski, A., Telle, J.A.: Covering regular graphs. J. Comb. Theory Ser. B\u00a071, 1\u201316 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/3-540-40996-3_39","volume-title":"Algorithms and Computation","author":"P. Kristiansen","year":"2000","unstructured":"Kristiansen, P., Telle, J.A.: Generalized H-coloring of graphs. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 456\u2013466. Springer, Heidelberg (2000)"},{"key":"14_CR26","unstructured":"Massey, W.S.: Algebraic Topology: An Introduction. Harcourt, Brace and World (1967)"},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0012-365X(71)90014-8","volume":"1","author":"J. Ne\u0161et\u0159il","year":"1971","unstructured":"Ne\u0161et\u0159il, J.: Homomorphisms of derivative graphs. Discr. Math.\u00a01, 257\u2013268 (1971)","journal-title":"Discr. Math."},{"key":"14_CR28","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0165-4896(00)00064-0","volume":"41","author":"A. Peke\u010d","year":"2001","unstructured":"Peke\u010d, A., Roberts, F.S.: The role assignment model nearly fits most social networks. Mathematical Social Sciences\u00a041, 275\u2013293 (2001)","journal-title":"Mathematical Social Sciences"},{"key":"14_CR29","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1002\/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9","volume":"37","author":"F.S. Roberts","year":"2001","unstructured":"Roberts, F.S., Sheng, L.: How hard is it to determine if a graph has a 2-role assignment? Networks\u00a037, 67\u201373 (2001)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40164-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T21:49:49Z","timestamp":1557956989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40164-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401633","9783642401640"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40164-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}