{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:17:17Z","timestamp":1742912237283,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_42","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"493-504","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of Covering Three-Vertex Multigraphs"],"prefix":"10.1007","author":[{"given":"Jan","family":"Kratochv\u00edl","sequence":"first","affiliation":[]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Tesa\u0159","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","first-page":"103","volume":"4","author":"J. Abello","year":"1991","unstructured":"Abello, J., Fellows, M.R., Stillwell, J.C.: On the complexity and combinatorics of covering finite complexes. Australian Journal of Combinatorics\u00a04, 103\u2013112 (1991)","journal-title":"Australian Journal of Combinatorics"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"issue":"2","key":"42_CR3","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. Journal of Combinatorial Theory, Series B\u00a030(2), 184\u2013187 (1981)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"42_CR4","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. Journal of Parallel and Distributed Computing\u00a06, 166\u2013182 (1989)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"42_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a\u00a03-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"42_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/321556.321562","volume":"17","author":"D.G. Corneil","year":"1970","unstructured":"Corneil, D.G., Gotlieb, C.C.: An Efficient Algorithm for Graph Isomorphism. J. ACM\u00a017(1), 51\u201364 (1970)","journal-title":"J. ACM"},{"issue":"2","key":"42_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/eujc.1994.1015","volume":"15","author":"B. Courcelle","year":"1994","unstructured":"Courcelle, B., M\u00e9tivier, Y.: Coverings and Minors: Application to Local Computations in Graphs. European Journal of Combinatorics\u00a015(2), 127\u2013138 (1994)","journal-title":"European Journal of Combinatorics"},{"key":"42_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"1","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM Journal of Computing\u00a01, 57\u2013104 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"42_CR9","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-structure, complexity, and applications. Computer Science Review\u00a02, 97\u2013111 (2008)","journal-title":"Computer Science Review"},{"key":"42_CR10","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"},{"issue":"1","key":"42_CR11","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/(SICI)1097-0118(199801)27:1<51::AID-JGT8>3.0.CO;2-F","volume":"21","author":"P. Hlin\u011bn\u00fd","year":"1998","unstructured":"Hlin\u011bn\u00fd, P.: K\n                           4,4\u2009\u2212\u2009e Has No Finite Planar Cover. Journal of Graph Theory\u00a021(1), 51\u201360 (1998)","journal-title":"Journal of Graph Theory"},{"issue":"3","key":"42_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/jgt.10177","volume":"46","author":"P. Hlin\u011bn\u00fd","year":"2004","unstructured":"Hlin\u011bn\u00fd, P., Thomas, R.: On possible counterexamples to Negami\u2019s planar cover conjecture. Journal of Graph Theory\u00a046(3), 183\u2013206 (2004)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"42_CR13","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The NP-Completeness of Edge-Coloring. SIAM J. Comput.\u00a010(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"42_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-540-39890-5_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kratochv\u00edl","year":"2003","unstructured":"Kratochv\u00edl, J.: Complexity of Hypergraph Coloring and Seidel\u2019s Switching. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 297\u2013308. Springer, Heidelberg (2003)"},{"issue":"1","key":"42_CR15","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. Journal of Combinatorial Theory, Series B\u00a071(1), 1\u201316 (1997)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"42_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/BFb0024502","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kratochv\u00edl","year":"1997","unstructured":"Kratochv\u00edl, J., Proskurowski, A., Telle, J.A.: Complexity of colored graph covers I. Colored directed multigraphs. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 242\u2013257. Springer, Heidelberg (1997)"},{"key":"42_CR17","first-page":"173","volume":"5","author":"J. Kratochv\u00edl","year":"1998","unstructured":"Kratochv\u00edl, J., Proskurowski, A., Telle, J.A.: Complexity of graph covering problems. Nordic Journal of Computing\u00a05, 173\u2013195 (1998)","journal-title":"Nordic Journal of Computing"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/3-540-56402-0_58","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"I. Litovsky","year":"1993","unstructured":"Litovsky, I., M\u00e9tivier, Y., Zielonka, W.: The power and the limitations of local computations on graphs. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol.\u00a0657, pp. 333\u2013345. Springer, Heidelberg (1993)"},{"key":"42_CR19","first-page":"377","volume":"4","author":"S. Negami","year":"1988","unstructured":"Negami, S.: Graphs which have no planar covering. Bulletin of the Institute of Mathematics, Academia Sinica\u00a04, 377\u2013384 (1988)","journal-title":"Bulletin of the Institute of Mathematics, Academia Sinica"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T20:17:33Z","timestamp":1676405853000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}