{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T18:03:26Z","timestamp":1757700206821,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,11,1]],"date-time":"2012-11-01T00:00:00Z","timestamp":1351728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP1094516DP110101104"],"award-info":[{"award-number":["DP1094516DP110101104"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>The crosscap number of a knot is an invariant describing the nonorientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above.<\/jats:p><jats:p>The first two algorithms advance the theoretical state-of-the-art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.<\/jats:p>","DOI":"10.1145\/2382585.2382589","type":"journal-article","created":{"date-parts":[[2012,12,5]],"date-time":"2012-12-05T18:55:48Z","timestamp":1354733748000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Computing the Crosscap Number of a Knot Using Integer Programming and Normal Surfaces"],"prefix":"10.1145","volume":"39","author":[{"given":"Benjamin A.","family":"Burton","sequence":"first","affiliation":[{"name":"The University of Queensland"}]},{"given":"Melih","family":"Ozlen","sequence":"additional","affiliation":[{"name":"RMIT University"}]}],"member":"320","published-online":{"date-parts":[[2012,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.010"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2010.01.031"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2004.10504538"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2010.10390625"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998220"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Burton B. A. and Ozlen M. 2010. A tree traversal algorithm for decision problems in knot theory and 3-manifold topology. Algorithmica (To appear). DOI 10.1007\/s00453-012-9645-3. Burton B. A. and Ozlen M. 2010. A tree traversal algorithm for decision problems in knot theory and 3-manifold topology. Algorithmica (To appear). DOI 10.1007\/s00453-012-9645-3.","DOI":"10.1145\/1998196.1998219"},{"key":"e_1_2_1_8_1","unstructured":"Burton B. A. Budney R. Pettersson W. etal 1999--2011. Regina: Software for 3-manifold topology and normal surface theory. http:\/\/regina.sourceforge.net\/. Burton B. A. Budney R. Pettersson W. et al. 1999--2011. Regina: Software for 3-manifold topology and normal surface theory. http:\/\/regina.sourceforge.net\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05419-X"},{"key":"e_1_2_1_10_1","unstructured":"Cha J. C. and Livingston C. 2011. KnotInfo: Table of knot invariants. http:\/\/www.indiana.edu\/~knotinfo. Cha J. C. and Livingston C. 2011. KnotInfo: Table of knot invariants. http:\/\/www.indiana.edu\/~knotinfo."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1155\/S0161171278000149"},{"volume":"6655","volume-title":"Integer Progamming and Combinatorial Optimization. Lecture Notes in Computer Science","author":"Cook W.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","unstructured":"Culler M. Dunfield N. M. and Weeks J. R. 1991--2011. SnapPy a computer program for studying the geometry and topology of 3-manifolds. http:\/\/snappy.computop.org\/. Culler M. Dunfield N. M. and Weeks J. R. 1991--2011. SnapPy a computer program for studying the geometry and topology of 3-manifolds. http:\/\/snappy.computop.org\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02559591"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"volume-title":"The Classification of Knots and 3-Dimensional Spaces","author":"Hemion G.","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198596974.001.0001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.top.2005.11.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2009.04.031"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(01)00188-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(89)90067-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1090503053"},{"key":"e_1_2_1_22_1","unstructured":"Jaco W. and Rubinstein J. H. 2006. Layered-triangulations of 3-manifolds. Preprint arXiv:math\/0603601. Jaco W. and Rubinstein J. H. 2006. Layered-triangulations of 3-manifolds. Preprint arXiv:math\/0603601."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0040-9383(02)00083-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255986385"},{"volume-title":"Algorithmic Topology and Classification of 3-Manifolds. Number 9 in Algorithms and Computation in Mathematics","author":"Matveev S.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1995.171.261"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2003.08.004"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382585.2382589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2382585.2382589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:38Z","timestamp":1750239278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382585.2382589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["10.1145\/2382585.2382589"],"URL":"https:\/\/doi.org\/10.1145\/2382585.2382589","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2012,11]]},"assertion":[{"value":"2011-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}