Conférence de Benjamin Burton
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.
Catégories: Séminaire général du département d'informatique
Mot-clés : mathématiques, diagramme, algorithme
Voir aussi
|
|
Université de Queensland
Chargé de recherche
Plus sur cet auteur
Voir la fiche de l'auteur
Cursus :
Benjamin Burton est un mathématicien, chercheur à l'École de mathématiques et de physique à l'Université du Queensland en Australie.
Cliquer ICI pour fermerDernière mise à jour : 19/12/2013
Tous droits réservés
@ 2011 ENS