A tree traversal algorithm for decision problems in knot theory and 3-manifold topology

Burton, B and Ozlen, M 2013, 'A tree traversal algorithm for decision problems in knot theory and 3-manifold topology', Algorithmica: An International Journal in Computer Science, vol. 65, no. 4, pp. 772-801.


Document type: Journal Article
Collection: Journal Articles

Attached Files
Name Description MIMEType Size
n2006038436.pdf Accepted Manuscript application/pdf 435.05KB
Title A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
Author(s) Burton, B
Ozlen, M
Year 2013
Journal name Algorithmica: An International Journal in Computer Science
Volume number 65
Issue number 4
Start page 772
End page 801
Total pages 30
Publisher Springer New York
Abstract In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a tree traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.
Subject Analysis of Algorithms and Complexity
Operations Research
Topology
Keyword(s) Backtracking
linear programming
normal surfaces
tree traversal
vertex enumeration
DOI - identifier 10.1007/s00453-012-9645-3
Copyright notice © Springer Science+Business Media, LLC 2012
ISSN 0178-4617
Additional Notes This is a post-peer-review, pre-copyedit version of an article published in Algorithmica: An International Journal in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00453-012-9645-3
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 105 Abstract Views, 11 File Downloads  -  Detailed Statistics
Created: Mon, 25 Feb 2013, 12:01:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us