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

Burton, Benjamin A. and Ozlen, Melih (2011). A tree traversal algorithm for decision problems in knot theory and 3-manifold topology. In: , SCoG '11: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry. 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, France, (145-152). 13-15 June 2011.

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 of paper A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
Conference Paper Type Fully Published Paper
Conference name 27th Annual Symposium on Computational Geometry (SoCG 2011)    (ERA 2010 Rank A)
DOI 10.1145/1998196.1998219
Conference location Paris, France
Conference dates 13-15 June 2011
Proceedings title SCoG '11: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry
Journal name Computational Geometry (Scg 11)
Place published New York, NY, United States
Publisher ACM Press
Publication date 2011
ISBN 9781450306829
Start page 145
End page 152
Total pages 8
Collection year 2012
Language eng
Abstract/Summary 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.
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Sub-type: Fully Published Paper
Collections: School of Mathematics and Physics
Official 2012 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Access Statistics: 47 Abstract Views, 1 File Downloads  -  Detailed Statistics
Created: Wed, 29 Jun 2011, 07:23:43 EST by Dr Benjamin Burton on behalf of School of Mathematics & Physics