A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
DOI10.1007/s00453-012-9645-3zbMath1270.57060arXiv1010.6200WikidataQ58644681 ScholiaQ58644681MaRDI QIDQ1949747
Benjamin A. Burton, Melih Özlen
Publication date: 16 May 2013
Published in: Algorithmica, Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.6200
68W30: Symbolic computation and algebraic computation
52B55: Computational aspects related to convexity
57N35: Embeddings and immersions in topological manifolds
90C05: Linear programming
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
- Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I
- An algorithm to decide if a 3-manifold is a Haken manifold
- Normal surfaces in topologically finite 3-manifolds
- Notes on Perelman's papers
- Converting between quadrilateral and standard solution sets in normal surface theory
- A polynomial Newton method for linear programming
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Normal surface \(Q\)-theory
- How good are convex hull algorithms?
- Maximal admissible faces and asymptotic bounds for the normal surface solution space
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- On the average number of steps of the simplex method of linear programming
- The Weber-Seifert dodecahedral space is non-Haken
- The computational complexity of knot and link problems
- The Complexity of Vertex Enumeration Methods
- Optimizing the double description method for normal surface enumeration
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- An Algorithm for Finding All Vertices of Convex Polyhedral Sets
- New Finite Pivoting Rules for the Simplex Method
- Lectures on Polytopes
- Computing Arithmetic Invariants of 3-Manifolds
- The complexity of the normal surface solution space
- Introducing Regina, The 3-Manifold Topology Software
- The maximum numbers of faces of a convex polytope
- Algorithmic topology and classification of 3-manifolds
