{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:41:51Z","timestamp":1787496111120,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_5","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"38-49","source":"Crossref","is-referenced-by-count":10,"title":["On Counting Homomorphisms to Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1109\/SFCS.2003.1238229","volume-title":"Proc. 44th IEEE Symposium on Foundations of Computer Science","author":"A. Bulatov","year":"2003","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. In: Proc. 44th IEEE Symposium on Foundations of Computer Science, pp. 562\u2013572. IEEE, Los Alamitos (2003)"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-27836-8_27","volume-title":"Automata, Languages and Programming","author":"A. Bulatov","year":"2004","unstructured":"Bulatov, A., Grohe, M.: The complexity of partition functions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 294\u2013306. Springer, Heidelberg (2004)"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M. Dyer","year":"2000","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. Random Structures & Algorithms\u00a017, 260\u2013289 (2000)","journal-title":"Random Structures & Algorithms"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/(SICI)1097-0037(199707)29:4<219::AID-NET5>3.0.CO;2-I","volume":"29","author":"S. Even","year":"1997","unstructured":"Even, S., Litman, A.: Layered cross product: a technique to construct interconnection networks. Networks\u00a029, 219\u2013223 (1997)","journal-title":"Networks"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput.\u00a0(28), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"B 48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory Series\u00a0B 48, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory Series"},{"key":"5_CR7","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 University Press, Oxford (2004)"},{"key":"5_CR8","volume-title":"Product graphs: structure and recognition","author":"W. Imrich","year":"2000","unstructured":"Imrich, W., Klav\u017ear, S.: Product graphs: structure and recognition. Wiley, New York (2000)"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02280291","volume":"18","author":"L. Lov\u00e1sz","year":"1967","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta. Math. Acad. Sci. Hung.\u00a018, 321\u2013328 (1967)","journal-title":"Acta. Math. Acad. Sci. Hung."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:53Z","timestamp":1619493593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/11786986_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}