{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:35:34Z","timestamp":1780382134279,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,8,4]],"date-time":"2011-08-04T00:00:00Z","timestamp":1312416000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00037-011-0018-0","type":"journal-article","created":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T19:16:09Z","timestamp":1312398969000},"page":"359-419","source":"Crossref","is-referenced-by-count":4,"title":["Complexity and Approximability of the Cover Polynomial"],"prefix":"10.1007","volume":"21","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Holger","family":"Dell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahmoud","family":"Fouz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,8,4]]},"reference":[{"issue":"1\u20133","key":"18_CR1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"Andrzejak Artur","year":"1998","unstructured":"Artur Andrzejak (1998) An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Mathematics 190(1\u20133): 39\u201354","journal-title":"Discrete Mathematics"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Ilia Averbouch , Benny Godlin & Johann A. Makowsky (2008). A Most General Edge Elimination Polynomial. In Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 \u2013 July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, 31\u201342.","DOI":"10.1007\/978-3-540-92248-3_4"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski & Mikko Koivisto (2008). Computing the Tutte polynomial in vertex-exponential time.","DOI":"10.1109\/FOCS.2008.40"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Markus Bl\u00e4ser, Holger Dell & Johann A. Makowsky (2008). Complexity of the Bollob\u00e1s-Riordan Polynomial. In 3rd International Computer Science Symposium in Russia (CSR), 86\u201398.","DOI":"10.1007\/978-3-540-79709-8_12"},{"key":"18_CR5","unstructured":"Markus Bl\u00e4ser & Christian Hoffmann (2008). On the Complexity of the Interlace Polynomial. In 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Susanne Albers & Pascal Weil, editors, 97\u2013108. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1337"},{"key":"18_CR6","unstructured":"Markus Bl\u00e4ser & Christian Hoffmann (2009). Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth. In Algorithms-ESA 2009, 17th Annual European Symposium, volume 5757 of Lecture Notes in Computer Science, 623\u2013634. Springer."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Lenore Blum, Felipe Cucker, Michael Shub & Steve Smale (1998). Complexity and real computation. Springer-Verlag New York, Inc., Secaucus, NJ, USA. ISBN 0-387-98281-7.","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"1\u20132","key":"18_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1017\/S0963548398003447","volume":"8","author":"Bollob\u00e1s B\u00e9la","year":"1999","unstructured":"B\u00e9la Bollob\u00e1s, Oliver Riordan (1999) A Tutte Polynomial for Coloured Graphs. Combinatorics, Probability and Computing 8(1\u20132): 45\u201393","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"18_CR9","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"Bulatov Andrei","year":"2005","unstructured":"Andrei Bulatov, Martin Grohe (2005) The complexity of partition functions. Theoretical Computer Science 348(2): 148\u2013186","journal-title":"Theoretical Computer Science"},{"key":"18_CR10","unstructured":"Timothy Y. Chow (1996). A Short Proof of the Rook Reciprocity Theorem. Electr. J. Comb. 3(1)."},{"issue":"2","key":"18_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1006\/jctb.1995.1055","volume":"65","author":"Chung Fan R.K.","year":"1995","unstructured":"Fan R.K. Chung, Ronald L. Graham (1995) On the cover polynomial of a digraph. Journal of Combinatorial Theory Series B 65(2): 273\u2013290","journal-title":"Journal of Combinatorial Theory Series B"},{"issue":"1\u20132","key":"18_CR12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"Courcelle Bruno","year":"2001","unstructured":"Bruno Courcelle, Johann A. Makowsky, Udi Rotics (2001) On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108(1\u20132): 23\u201352","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"18_CR13","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/aama.2000.0689","volume":"25","author":"D\u2019Antona Ottavio M.","year":"2000","unstructured":"Ottavio M. D\u2019Antona, Emanuele Munarini (2000) The cycle-path indicator polynomial of a digraph. Adv. Appl. Math. 25(1): 41\u201356","journal-title":"Adv. Appl. Math."},{"key":"18_CR14","unstructured":"Martin Dyer, Alan Frieze & Mark Jerrum (2002). On Counting Independent Sets in Sparse Graphs. SICOMP: SIAM Journal on Computing 31."},{"issue":"5","key":"18_CR15","doi-asserted-by":"crossref","first-page":"1262","DOI":"10.1137\/S009753979426112X","volume":"27","author":"Dyer Martin E.","year":"1998","unstructured":"Martin E. Dyer, Alan M. Frieze, Mark Jerrum (1998) Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM Journal on Computing 27(5): 1262\u20131272","journal-title":"SIAM Journal on Computing"},{"key":"18_CR16","unstructured":"Martin E. Dyer, Leslie Ann Goldberg & Mike Paterson (2006). On Counting Homomorphisms to Directed Acyclic Graphs. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, volume 4051 of Lecture Notes in Computer Science, 38\u201349. Springer."},{"key":"18_CR17","unstructured":"Michael R. Garey & David S. Johnson (1979). Computers and Intractability. Freeman, San Francisco."},{"issue":"3","key":"18_CR18","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1017\/S0963548305007327","volume":"15","author":"Gim\u00e9nez Omer","year":"2006","unstructured":"Omer Gim\u00e9nez, Marc Noy (2006) On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids. Combinatorics, Probability and Computing 15(3): 385\u2013395","journal-title":"Combinatorics, Probability and Computing"},{"issue":"7","key":"18_CR19","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1016\/j.ic.2008.04.003","volume":"206","author":"Goldberg Leslie Ann","year":"2008","unstructured":"Leslie Ann Goldberg, Mark Jerrum (2008) Inapproximability of the Tutte polynomial. Inform. Comput. 206(7): 908\u2013929","journal-title":"Inform. Comput."},{"issue":"4","key":"18_CR20","doi-asserted-by":"crossref","first-page":"373","DOI":"10.3233\/FI-2010-233","volume":"98","author":"Hoffmann Christian","year":"2010","unstructured":"Christian Hoffmann (2010) A Most General Edge Elimination Polynomial - Thickening of Edges. Fundam. Inform. 98(4): 373\u2013378","journal-title":"Fundam. Inform."},{"issue":"1","key":"18_CR21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"Jaeger Fran\u00e7ois","year":"1990","unstructured":"Fran\u00e7ois Jaeger, Dirk L. Vertigan, Dominic J.A. Welsh (1990) On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society 108(1): 35\u201353","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"issue":"1","key":"18_CR22","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"Jerrum Mark","year":"1989","unstructured":"Mark Jerrum, Alistair Sinclair (1989) Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. Information and Computation 82(1): 93\u2013133","journal-title":"Information and Computation"},{"key":"18_CR23","unstructured":"Mark Jerrum & Alistair Sinclair (1997). The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, editor. PWS Publishing Company."},{"key":"18_CR24","unstructured":"Mark Jerrum, Alistair Sinclair & Eric Vigoda (2004). A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries. JACM: Journal of the ACM 51."},{"issue":"2","key":"18_CR25","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"Linial Nathan","year":"1986","unstructured":"Nathan Linial (1986) Hard enumeration problems in geometry and combinatorics. SIAM J. Algebraic Discrete Methods 7(2): 331\u2013335","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"18_CR26","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0196-8858(03)00087-3","volume":"32","author":"Lotz Martin","year":"2004","unstructured":"Martin Lotz, Johann A. Makowsky (2004) On the algebraic complexity of some families of coloured Tutte polynomials. Advances in Applied Mathematics 32(1): 327\u2013349","journal-title":"Advances in Applied Mathematics"},{"issue":"3","key":"18_CR27","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"Makowsky Johann A.","year":"2008","unstructured":"Johann A. Makowsky (2008) From a zoo to a zoology: Towards a general theory of graph polynomials. Theory of Computing Systems 43(3): 542\u2013562","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"18_CR28","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"S.D. Noble","year":"1998","unstructured":"Noble S.D. (1998) Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width. Combinatorics, Probability & Computing 7(3): 307\u2013321","journal-title":"Combinatorics, Probability & Computing"},{"key":"18_CR29","volume-title":"Computational Complexity","author":"Papadimitriou Christos M.","year":"1994","unstructured":"Christos M. Papadimitriou (1994) Computational Complexity. Addison-Wesley, Reading, Massachusetts"},{"issue":"2","key":"18_CR30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"Valiant Leslie G.","year":"1979","unstructured":"Leslie G. Valiant (1979) The complexity of computing the permanent. Theoretical Computer Science 8(2): 189\u2013201","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR31","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"Valiant Leslie G.","year":"1986","unstructured":"Leslie G. Valiant, Vijay V. Vazirani (1986) NP is as easy as detecting unique solutions. Theoretical Computer Science 47(1): 85\u201393","journal-title":"Theoretical Computer Science"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0018-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0018-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0018-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:14:19Z","timestamp":1592784859000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0018-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,4]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["18"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0018-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,4]]}}}