2:00 pm, Seminar Hall
Untangling knots using combinatorial optimisation
Benjamin Burton
Computational Geometry & Topology Group, University of Queensland, Australia.
17-11-14

---

Abstract

Unknot recognition is the algorithmic problem of determining whether a knot (i.e., a closed loop) in 3-dimensional space can be untangled. It is a major unsolved question as to whether this problem has a polynomial time solution. Here we present the first conclusive algorithm for unknot recognition which, although exponential time in theory, exhibits a clear polynomial time behaviour in exhaustive practical experiments. The algorithm marries together techniques from computational topology and combinatorial optimisation, and gives a glimpse of the rich potential that integer and linear programming have to offer in the world of 3-dimensional geometry and topology.