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

Burton, Benjamin A. and Ozlen, Melih (2013) A tree traversal algorithm for decision problems in knot theory and 3-manifold topology. Algorithmica, 65 4: 772-801. doi:10.1007/s00453-012-9645-3

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Burton, Benjamin A.
Ozlen, Melih
Title A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
Journal name Algorithmica   Check publisher's open access policy
ISSN 0178-4617
1432-0541
Publication date 2013-04
Year available 2012
Sub-type Article (original research)
DOI 10.1007/s00453-012-9645-3
Open Access Status
Volume 65
Issue 4
Start page 772
End page 801
Total pages 30
Place of publication Secaucus, NJ, United States
Publisher Springer
Collection year 2013
Language eng
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.
Keyword Normal surfaces
Vertex enumeration
Tree traversal
Backtracking
Linear programming
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Published online 12 May 2012.

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2013 Collection
ERA White List Items
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 3 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 10 Mar 2013, 00:50:22 EST by System User on behalf of Scholarly Communication and Digitisation Service