{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:21Z","timestamp":1740109281114,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T00:00:00Z","timestamp":1536105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0511-9","type":"journal-article","created":{"date-parts":[[2018,9,5]],"date-time":"2018-09-05T11:19:39Z","timestamp":1536146379000},"page":"1844-1858","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph"],"prefix":"10.1007","volume":"81","author":[{"given":"Viresh","family":"Patel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guus","family":"Regts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,5]]},"reference":[{"issue":"1","key":"511_CR1","first-page":"7","volume":"8","author":"N Alon","year":"1999","unstructured":"Alon, N., Tarsi, M.: Combinatorics probability and computing. Combinatorial nullstellensatz 8(1), 7\u201330 (1999)","journal-title":"Combinatorial nullstellensatz"},{"key":"511_CR2","doi-asserted-by":"crossref","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, 21\u201323 Nov 2002, Proceedings, pp. 453\u2013464 (2002)","DOI":"10.1007\/3-540-36136-7_40"},{"key":"511_CR3","volume-title":"Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics","author":"A Barvinok","year":"2017","unstructured":"Barvinok, A.: Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer, Berlin (2017)"},{"key":"511_CR4","unstructured":"Barvinok, A., Regts, G.: Weighted counting of non-negative integer points in a subspace (2017). arXiv preprint \n                    arXiv:1706.05423"},{"issue":"1","key":"511_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20414","volume":"42","author":"C Borgs","year":"2013","unstructured":"Borgs, C., Chayes, J., Kahn, J., Lov\u00e1sz, L.: Left and right convergence of graphs with bounded degree. Random Struct. Algorithms 42(1), 1\u201328 (2013)","journal-title":"Random Struct. Algorithms"},{"key":"511_CR6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Thurley, M., Weyer, M.: Understanding the complexity of induced subgraph isomorphisms. In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, 7\u201311 July 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pp. 587\u2013596 (2008)","DOI":"10.1007\/978-3-540-70575-8_48"},{"key":"511_CR7","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.ejc.2015.07.009","volume":"52","author":"P Csikv\u00e1ri","year":"2016","unstructured":"Csikv\u00e1ri, P., Frenkel, P.E.: Benjamini\u2013Schramm continuity of root moments of graph polynomials. Eur. J. Comb. 52, 302\u2013320 (2016)","journal-title":"Eur. J. Comb."},{"key":"511_CR8","unstructured":"Curticapean, R., Dell, H., Fomin, F.V., Goldberg, L.A., Lapinskas, J.: A fixed-parameter perspective on #bis. In: 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, 6\u20138 Sept 2017, Vienna, Austria, pp. 13:1\u201313:13 (2017)"},{"key":"511_CR9","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 210\u2013223 (2017)","DOI":"10.1145\/3055399.3055502"},{"key":"511_CR10","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Marx, D.: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 Oct 2014, pp. 130\u2013139 (2014)","DOI":"10.1109\/FOCS.2014.22"},{"issue":"1&2","key":"511_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"511_CR12","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"511_CR13","unstructured":"Johnson, D.S., Szegedy, M.: What are the least tractable instances of max independent set? In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17\u201319 Jan 1999, Baltimore, Maryland, pp. 927\u2013928 (1999)"},{"key":"511_CR14","doi-asserted-by":"crossref","unstructured":"Liu, J., Sinclair, A., Srivastava, P.: The Ising partition function: Zeros and deterministic approximation. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 Oct 2017, pp. 986\u2013997 (2017)","DOI":"10.1109\/FOCS.2017.95"},{"key":"511_CR15","volume-title":"Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz, L.: Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence (2012)"},{"key":"511_CR16","unstructured":"Nederlof, J.: Personal communication"},{"issue":"2","key":"511_CR17","first-page":"415","volume":"26","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carolin. 26(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carolin."},{"issue":"6","key":"511_CR18","doi-asserted-by":"publisher","first-page":"1893","DOI":"10.1137\/16M1101003","volume":"46","author":"V Patel","year":"2017","unstructured":"Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893\u20131919 (2017)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"511_CR19","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1007\/s10955-004-2055-4","volume":"118","author":"AD Scott","year":"2005","unstructured":"Scott, A.D., Sokal, A.D.: The repulsive lattice gas, the independent-set polynomial, and the Lov\u00e1sz local lemma. J. Stat. Phys. 118(5), 1151\u20131261 (2005)","journal-title":"J. Stat. Phys."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0511-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0511-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0511-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T20:43:03Z","timestamp":1569271383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0511-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,5]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["511"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0511-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,9,5]]},"assertion":[{"value":"21 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}