{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T21:12:46Z","timestamp":1764364366186,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP1094516","DP140104246"],"award-info":[{"award-number":["DP1094516","DP140104246"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s41468-018-0016-2","type":"journal-article","created":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T12:36:13Z","timestamp":1534941373000},"page":"33-53","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms and complexity for Turaev\u2013Viro invariants"],"prefix":"10.1007","volume":"2","author":[{"given":"Benjamin A.","family":"Burton","sequence":"first","affiliation":[]},{"given":"Cl\u00e9ment","family":"Maria","sequence":"additional","affiliation":[]},{"given":"Jonathan","family":"Spreer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"issue":"1\u20132","key":"16_CR1","first-page":"125","volume":"17","author":"G Alagic","year":"2017","unstructured":"Alagic, G., Lo, C.: Quantum invariants of $$3$$-manifolds and NP vs. #P. Quantum Inf. Comput. 17(1\u20132), 125\u2013146 (2017)","journal-title":"Quantum Inf. Comput."},{"issue":"4","key":"16_CR2","doi-asserted-by":"publisher","first-page":"040302(R)","DOI":"10.1103\/PhysRevA.82.040302","volume":"82","author":"G Alagic","year":"2010","unstructured":"Alagic, G., Jordan, S.P., K\u00f6nig, R., Reichardt, B.W.: Estimating Turaev\u2013Viro three-manifold invariants is universal for quantum computation. Phys. Rev. A 82(4), 040302(R) (2010)","journal-title":"Phys. Rev. A"},{"issue":"4","key":"16_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/s00453-008-9180-4","volume":"56","author":"E Amir","year":"2010","unstructured":"Amir, E.: Approximation algorithms for treewidth. Algorithmica 56(4), 448\u2013479 (2010). \n                    https:\/\/doi.org\/10.1007\/s00453-008-9180-4","journal-title":"Algorithmica"},{"issue":"2","key":"16_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"3997","DOI":"10.1090\/S0002-9947-96-01660-1","volume":"348","author":"JW Barrett","year":"1996","unstructured":"Barrett, J.W., Westbury, B.W.: Invariants of piecewise-linear 3-manifolds. Trans. Am. Math. Soc. 348, 3997\u20134022 (1996)","journal-title":"Trans. Am. Math. Soc."},{"issue":"6","key":"16_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996). \n                    https:\/\/doi.org\/10.1137\/S0097539793251219","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations. I. Upper bounds. Inf. Comput. 208(3), 259\u2013275 (2010). \n                    https:\/\/doi.org\/10.1016\/j.ic.2009.03.008","journal-title":"Inf. Comput."},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c$${}^{\\text{ k }}$$ n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016). \n                    https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Comput."},{"issue":"5","key":"16_CR9","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1142\/S0218216507005439","volume":"16","author":"BA Burton","year":"2007","unstructured":"Burton, B.A.: Structures of small closed non-orientable 3-manifold triangulations. J. Knot Theory Ramif. 16(5), 545\u2013574 (2007)","journal-title":"J. Knot Theory Ramif."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Burton, B.A.: Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations. In: ISSAC 2011: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp. 59\u201366. ACM, New York (2011)","DOI":"10.1145\/1993886.1993901"},{"key":"16_CR11","unstructured":"Burton, B.A., Budney, R., Pettersson, W., et\u00a0al.: Regina: software for 3-manifold topology and normal surface theory (1999\u20132014). \n                    http:\/\/regina.sourceforge.net\/"},{"key":"16_CR12","unstructured":"Burton, B.A., Downey, R.G.: Courcelle\u2019s theorem for triangulations (2014) (preprint). \n                    arXiv:1403.2926"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-662-47672-7_23","volume-title":"Automata, Languages, and Programming","author":"Benjamin A. Burton","year":"2015","unstructured":"Burton, B.A., Maria, C., Spreer, J.: Algorithms and complexity for Turaev\u2013Viro invariants. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 281\u2013293 (2015)"},{"issue":"7","key":"16_CR14","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"DG Cantor","year":"1991","unstructured":"Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28(7), 693\u2013701 (1991). \n                    https:\/\/doi.org\/10.1007\/BF01178683","journal-title":"Acta Inform."},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629\u2013657 (2008). \n                    https:\/\/doi.org\/10.1137\/05064299X","journal-title":"SIAM J. Comput."},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1080\/10586458.1994.10504296","volume":"3","author":"CD Hodgson","year":"1994","unstructured":"Hodgson, C.D., Weeks, J.R.: Symmetries, isometries and length spectra of closed hyperbolic three-manifolds. Exp. Math. 3(4), 261\u2013274 (1994)","journal-title":"Exp. Math."},{"key":"16_CR17","unstructured":"Husz\u00e1r, K., Spreer, J., Wagner, U.: On the treewidth of triangulated 3-manifolds. In: 34nd International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPICS), vol. 99, pp. 46:1\u201346:15 (2018)"},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02568267","volume":"72","author":"LH Kauffman","year":"1991","unstructured":"Kauffman, L.H., Lins, S.: Computing Turaev\u2013Viro invariants for $$3$$-manifolds. Manuscripta Math. 72(1), 81\u201394 (1991)","journal-title":"Manuscripta Math."},{"key":"16_CR19","doi-asserted-by":"publisher","unstructured":"Kirby, R., Melvin, P.: Local surgery formulas for quantum invariants and the Arf invariant. In: Proceedings of the Casson Fest. Geometry and Topology Monographs, vol.\u00a07, pp. 213\u2013233. Geometry and Topology Publishers, Coventry (2004). \n                    https:\/\/doi.org\/10.2140\/gtm.2004.7.213","DOI":"10.2140\/gtm.2004.7.213"},{"issue":"5","key":"16_CR20","doi-asserted-by":"publisher","first-page":"2587","DOI":"10.2140\/gt.2008.12.2587","volume":"12","author":"B Kleiner","year":"2008","unstructured":"Kleiner, B., Lott, J.: Notes on Perelman\u2019s papers. Geom. Topol. 12(5), 2587\u20132855 (2008)","journal-title":"Geom. Topol."},{"key":"16_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Springer, Berlin (1994)"},{"key":"16_CR22","unstructured":"Maria, C., Spreer, J.: A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2721\u20132732. ACM, New York (2017). \n                    arXiv:1607.02218"},{"issue":"3","key":"16_CR23","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"IL Markov","year":"2008","unstructured":"Markov, I.L., Shi, Y.: Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38(3), 963\u2013981 (2008). \n                    https:\/\/doi.org\/10.1137\/050644756","journal-title":"SIAM J. Comput."},{"key":"16_CR24","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05102-3","volume-title":"Algorithmic Topology and Classification of 3-Manifolds","author":"S Matveev","year":"2003","unstructured":"Matveev, S.: Algorithmic Topology and Classification of 3-Manifolds. Algorithms and Computation in Mathematics, vol. 9. Springer, Berlin (2003)"},{"key":"16_CR25","unstructured":"Matveev, S., et\u00a0al.: Manifold recognizer. \n                    http:\/\/www.matlas.math.csu.ru\/?page=recognizer\n                    \n                  . Accessed Aug 2012"},{"key":"16_CR26","volume-title":"Elements of Algebraic Topology","author":"JR Munkres","year":"1984","unstructured":"Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984)"},{"issue":"3","key":"16_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"5","key":"16_CR28","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991). \n                    https:\/\/doi.org\/10.1137\/0220053","journal-title":"SIAM J. Comput."},{"key":"16_CR29","series-title":"de Gruyter Studies in Mathematics","doi-asserted-by":"publisher","DOI":"10.1515\/9783110221848","volume-title":"Quantum Invariants of Knots and 3-Manifolds","author":"VG Turaev","year":"2010","unstructured":"Turaev, V.G.: Quantum Invariants of Knots and 3-Manifolds. de Gruyter Studies in Mathematics, vol. 18, revised edn. Walter de Gruyter & Co., Berlin (2010). \n                    https:\/\/doi.org\/10.1515\/9783110221848","edition":"revised"},{"issue":"4","key":"16_CR30","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1016\/0040-9383(92)90015-A","volume":"31","author":"VG Turaev","year":"1992","unstructured":"Turaev, V.G., Viro, O.Y.: State sum invariants of $$3$$-manifolds and quantum $$6j$$-symbols. Topology 31(4), 865\u2013902 (1992)","journal-title":"Topology"},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979). \n                    https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor. Comput. Sci."},{"key":"16_CR32","unstructured":"van Dijk, T., van\u00a0den Heuvel, J.P., Slob, W.: Computing treewidth with LibTW (2006). \n                    http:\/\/www.treewidth.com\/treewidth\/"},{"key":"16_CR33","unstructured":"Walker, K.: On Witten\u2019s 3-manifold invariants (1991). \n                    http:\/\/canyon23.net\/math\/"}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41468-018-0016-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-018-0016-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-018-0016-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T05:19:41Z","timestamp":1589692781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41468-018-0016-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,22]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["16"],"URL":"https:\/\/doi.org\/10.1007\/s41468-018-0016-2","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2018,8,22]]},"assertion":[{"value":"26 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}