{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T07:47:46Z","timestamp":1648626466164},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T00:00:00Z","timestamp":1573430400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T00:00:00Z","timestamp":1573430400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10208-019-09438-8","type":"journal-article","created":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T19:02:46Z","timestamp":1573498966000},"page":"1013-1034","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Polynomial-Time Algorithm to Compute Turaev\u2013Viro Invariants $$\\mathrm {TV}_{4,q}$$ of 3-Manifolds with Bounded First Betti Number"],"prefix":"10.1007","volume":"20","author":[{"given":"Cl\u00e9ment","family":"Maria","sequence":"first","affiliation":[]},{"given":"Jonathan","family":"Spreer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,11]]},"reference":[{"issue":"2","key":"9438_CR1","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"},{"issue":"6","key":"9438_CR2","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)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9438_CR3","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 Ramifications 16(5), 545\u2013574 (2007)","journal-title":"J. Knot Theory Ramifications"},{"key":"9438_CR4","doi-asserted-by":"crossref","unstructured":"Burton, B.A.: Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations. In: Proceedings of ISSAC, pp. 59\u201366. ACM (2011)","DOI":"10.1145\/1993886.1993901"},{"issue":"1","key":"9438_CR5","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00454-014-9572-y","volume":"52","author":"BA Burton","year":"2014","unstructured":"Burton, B.A.: A new approach to crushing 3-manifold triangulations. Discrete Comput. Geom. 52(1), 116\u2013139 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"9438_CR6","unstructured":"Burton, B.A., Budney, R., Pettersson, W., et\u00a0al.: Regina: Software for 3-manifold topology and normal surface theory. https:\/\/regina-normal.github.io\/ (1999\u20132019). Accessed 25 Oct 2019"},{"issue":"1\u20132","key":"9438_CR7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s41468-018-0016-2","volume":"2","author":"BA Burton","year":"2018","unstructured":"Burton, B.A., Maria, C., Spreer, J.: Algorithms and complexity for Turaev-Viro invariants. J. Appl. Comput. Topol. 2(1-2), 33\u201353 (2018)","journal-title":"J. Appl. Comput. Topol."},{"key":"9438_CR8","unstructured":"Burton, B.A., Ozlen, M.: A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour. arXiv:1211.1079 (2012)"},{"key":"9438_CR9","volume-title":"Computational topology: An introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.L.: Computational topology: An introduction. American Mathematical Society, Providence, RI (2010)"},{"issue":"2","key":"9438_CR10","doi-asserted-by":"publisher","first-page":"995","DOI":"10.4007\/annals.2009.170.995","volume":"170","author":"MH Freedman","year":"2009","unstructured":"Freedman, M.H.: Complexity classes as mathematical axioms. Ann. of Math 170(2), 995\u20131002 (2009)","journal-title":"Ann. of Math. (2)"},{"issue":"8","key":"9438_CR11","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1142\/S021821650800649X","volume":"17","author":"C Frohman","year":"2008","unstructured":"Frohman, C., Kania-Bartoszynska, J.: The quantum content of the normal surfaces in a three-manifold. J. Knot Theory Ramifications 17(8), 1005\u20131033 (2008)","journal-title":"J. Knot Theory Ramifications"},{"key":"9438_CR12","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"key":"9438_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09354-3","volume-title":"Mod two homology and cohomology","author":"JC Hausmann","year":"2014","unstructured":"Hausmann, J.C.: Mod two homology and cohomology. Universitext. Springer, Cham (2014)"},{"issue":"4","key":"9438_CR14","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. Experiment. Math. 3(4), 261\u2013274 (1994)","journal-title":"Experiment. Math."},{"key":"9438_CR15","unstructured":"Husz\u00e1r, K., Spreer, J.: 3-Manifold Triangulations with Small Treewidth. In: Proceedings of SOCG, pp. 44:1\u201344:20. LIPIcs (2019)"},{"key":"9438_CR16","unstructured":"Husz\u00e1r, K., Spreer, J., Wagner, U.: On the treewidth of triangulated 3-manifolds. In: Proceddings of SOCG, pp. 46:1\u201346:15. LIPIcs (2018)"},{"issue":"1","key":"9438_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.4310\/jdg\/1090503053","volume":"65","author":"W Jaco","year":"2003","unstructured":"Jaco, W., Rubinstein, J.H.: 0-Efficient Triangulations of 3-Manifolds. J. Differential Geom. 65(1), 61\u2013168 (2003)","journal-title":"J. Differential Geom."},{"issue":"1","key":"9438_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-Viro invariants for $$3$$-manifolds. Manuscripta Math. 72(1), 81\u201394 (1991)","journal-title":"Manuscripta Math."},{"key":"9438_CR19","doi-asserted-by":"crossref","unstructured":"Kirby, R., Melvin, P.: Local surgery formulas for quantum invariants and the Arf invariant. Geom. Topol. Monogr. pp. (7):213\u2013233 (2004)","DOI":"10.2140\/gtm.2004.7.213"},{"issue":"1","key":"9438_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2140\/pjm.2019.301.189","volume":"301","author":"G Kuperberg","year":"2019","unstructured":"Kuperberg, G.: Algorithmic homeomorphism of $$3$$-manifolds as a corollary of geometrization. Pacific J. Math. 301(1), 189\u2013241 (2019)","journal-title":"Pacific J. Math."},{"key":"9438_CR21","volume-title":"Finite Fields","author":"R Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)"},{"issue":"5","key":"9438_CR22","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.2140\/agt.2019.19.2625","volume":"19","author":"C Maria","year":"2019","unstructured":"Maria, C., Purcell, J.S.: Treewidth, crushing, and hyperbolic volume. Algebraic Geom. Topology 19(5), 2625\u20132652. https:\/\/doi.org\/10.2140\/agt.2019.19.2625 (2019)","journal-title":"Algebraic Geom. Topology"},{"key":"9438_CR23","unstructured":"Maria, C., Spreer, J.: Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants. In: Proceedings of ESA, pp. 64:1\u201364:16 (2016)"},{"key":"9438_CR24","unstructured":"Maria, C., Spreer, J.: Classification of normal curves on a tetrahedron. In: SOCG:YRF \u2013 Collection of Abstracts (2016)"},{"key":"9438_CR25","doi-asserted-by":"crossref","unstructured":"Maria, C., Spreer, J.: A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first betti number. In: Proceedings of SODA, pp. 2721\u20132732 (2017)","DOI":"10.1137\/1.9781611974782.180"},{"key":"9438_CR26","first-page":"218","volume":"121","author":"A Markov","year":"1958","unstructured":"Markov, A.: The insolubility of the problem of homeomorphy. Dokl. Akad. Nauk SSSR 121, 218\u2013220 (1958)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9438_CR27","unstructured":"Matveev, S.: Transformations of special spines, and the Zeeman conjecture. Izv. Akad. Nauk SSSR Ser. Mat. 51(5), 1104\u20131116, 1119 (1987)"},{"key":"9438_CR28","doi-asserted-by":"publisher","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. Springer, Berlin (2003)"},{"key":"9438_CR29","unstructured":"Matveev, S., et\u00a0al.: Manifold recognizer. http:\/\/www.matlas.math.csu.ru\/?page=recognizer (2012). Accessed 25 Oct 2019"},{"issue":"1","key":"9438_CR30","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6\u201326 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"9438_CR31","unstructured":"Morgan, J., Tian, G.: The geometrization conjecture. American Mathematical Society, Providence, RI; Clay Mathematics Institute, Cambridge, MA (2014)"},{"issue":"5","key":"9438_CR32","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1016\/j.jctb.2006.01.006","volume":"96","author":"S Norine","year":"2006","unstructured":"Norine, S., Seymour, P.D., Thomas, R., Wollan, P.: Proper minor-closed families are small. J. Comb 96(5), 754\u2013757 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9438_CR33","unstructured":"Piergallini, R.: Standard moves for standard polyhedra and spines. Rend. Circ. Mat. Palermo (2) Suppl. (18), 391\u2013414 (1988)"},{"issue":"1","key":"9438_CR34","first-page":"164","volume":"10","author":"S Schleimer","year":"2019","unstructured":"Schleimer, S., de\u00a0Mesmay, A., Purcell, J., Sedgwick, E.: On the tree-width of knot diagrams. Journal of Computational Geometry 10(1), 164\u2013180 (2019)","journal-title":"Journal of Computational Geometry"},{"issue":"3","key":"9438_CR35","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/BF02355426","volume":"61","author":"M Sokolov","year":"1997","unstructured":"Sokolov, M.: Which lens spaces are distinguished by Turaev\u2013Viro invariants? Mathematical Notes 61(3), 468\u2013470 (1997)","journal-title":"Mathematical Notes"},{"key":"9438_CR36","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical topology and combinatorial group theory","author":"J Stillwell","year":"1993","unstructured":"Stillwell, J.: Classical topology and combinatorial group theory, Graduate Texts in Mathematics, vol.\u00a072, Springer-Verlag, second edn. Springer-Verlag, New York (1993)","edition":"second"},{"key":"9438_CR37","unstructured":"Storjohann, A.: Algorithms for matrix canonical forms. Ph.D. thesis, ETH Z\u00fcrich (2000)"},{"key":"9438_CR38","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":"V.G Turaev","year":"2010","unstructured":"Turaev, V.G.: Quantum invariants of knots and 3-manifolds, de Gruyter Studies in Mathematics, vol.\u00a018, revised edn. Walter de Gruyter & Co., Berlin (2010)","edition":"revised"},{"issue":"4","key":"9438_CR39","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"},{"issue":"2","key":"9438_CR40","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1142\/S0218216595000156","volume":"4","author":"S Yamada","year":"1995","unstructured":"Yamada, S.: The absolute value of the Chern-Simons-Witten invariants of lens spaces. J. Knot Theory Ramifications 4(2), 319\u2013327 (1995)","journal-title":"J. Knot Theory Ramifications"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09438-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-019-09438-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09438-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,10]],"date-time":"2020-11-10T00:14:41Z","timestamp":1604967281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-019-09438-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,11]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9438"],"URL":"https:\/\/doi.org\/10.1007\/s10208-019-09438-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,11]]},"assertion":[{"value":"26 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}