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

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

2010-10-29

arxiv.org/abs/1010.6200v2

Mathematics

Geometric Topology

28 pages, 7 figures; v2: minor revisions; to appear in Algorithmica

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A tree traversal algorithm for decision problems in knot theory and 3-manifold topology does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A tree traversal algorithm for decision problems in knot theory and 3-manifold topology, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A tree traversal algorithm for decision problems in knot theory and 3-manifold topology will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615756