{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:25:46Z","timestamp":1766136346617},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,9,29]],"date-time":"2012-09-29T00:00:00Z","timestamp":1348876800000},"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,12]]},"DOI":"10.1007\/s00037-012-0046-4","type":"journal-article","created":{"date-parts":[[2012,9,30]],"date-time":"2012-09-30T11:39:21Z","timestamp":1349005161000},"page":"605-642","source":"Crossref","is-referenced-by-count":10,"title":["Inapproximability of the Tutte polynomial of a planar graph"],"prefix":"10.1007","volume":"21","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,9,29]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1090\/S0002-9947-1946-0018401-4","volume":"60","author":"G.D. Birkhoff","year":"1946","unstructured":"Birkhoff G.D., Lewis D.C. (1946) Chromatic polynomials. Trans. Amer. Math. Soc. 60: 355\u2013451 ISSN 0002-9947","journal-title":"Trans. Amer. Math. Soc."},{"issue":"4","key":"46_CR2","first-page":"826","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey M.R., Johnson D.S. (1977) The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4): 826\u2013834 ISSN 0036-1399","journal-title":"Appl. Math."},{"issue":"3","key":"46_CR3","first-page":"237","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey M.R., David S. Johnson., Larry J., Larry J. (1976) Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237\u2013267","journal-title":"Comput. Sci."},{"issue":"7","key":"46_CR4","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. and Comput. 206(7): 908\u2013929 ISSN 0890-5401","journal-title":"Inapproximability of the Tutte polynomial. Inform. and Comput."},{"key":"46_CR5","doi-asserted-by":"crossref","unstructured":"Bill Jackson & Alan D. Sokal (2009). Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids. J. Combin. Theory Ser. B 99(6), 869\u2013903. ISSN 0095-8956. doi: 10.1016\/j.jctb.2009.03.002 .","DOI":"10.1016\/j.jctb.2009.03.002"},{"issue":"1","key":"46_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger F., Vertigan D.L., Welsh D.J.A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108(1): 35\u201353 ISSN 0305-0041","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"46_CR7","doi-asserted-by":"crossref","unstructured":"Mark Jerrum (2003). Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich. Birkh\u00e4user Verlag, Basel. ISBN 3-7643-6946-9, xii+112.","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"46_CR8","unstructured":"Greg Kuperberg (2009). How hard is it to approximate the Jones polynomial? http:\/\/arxiv.org\/abs\/0908.0512 ."},{"key":"46_CR9","unstructured":"Christos H. Papadimitriou (1994). Computational complexity. Addison-Wesley Publishing Company, Reading, MA. ISBN 0-201-53082-1, xvi+523."},{"key":"46_CR10","doi-asserted-by":"crossref","unstructured":"Alan D. Sokal (2005). The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in combinatorics 2005, volume 327 of London Math. Soc. Lecture Note Ser., 173\u2013226. Cambridge Univ. Press, Cambridge. doi: 10.1017\/CBO9780511734885.009 .","DOI":"10.1017\/CBO9780511734885.009"},{"key":"46_CR11","unstructured":"W. T. Tutte (1984). Graph theory, volume 21 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company Advanced Book Program, Reading, MA. ISBN 0-201-13520-5, xxi+333. With a foreword by C. St. J. A. Nash-Williams."},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"Dirk Vertigan (2005). The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput. 35(3), 690\u2013712 (electronic). ISSN 0097-5397.","DOI":"10.1137\/S0097539704446797"},{"key":"46_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: knots, colourings and counting, volume 186 of London Mathematical Society Lecture Note Series","author":"D.J.A. Welsh","year":"1993","unstructured":"Welsh D.J.A. (1993) Complexity: knots, colourings and counting, volume 186 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge ISBN 0-521-45740-8, viii+163"},{"issue":"1-3","key":"46_CR14","first-page":"141","volume":"172","author":"D.R. Woodall","year":"1997","unstructured":"Woodall D.R. (1997) The largest real zero of the chromatic polynomial. Discrete Math. 172(1-3): 141\u2013153 ISSN 0012-365X","journal-title":"The largest real zero of the chromatic polynomial. Discrete Math."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0046-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0046-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0046-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,4]],"date-time":"2019-07-04T09:00:47Z","timestamp":1562230847000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0046-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,29]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["46"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0046-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,29]]}}}