A Polynomial time Algorithm for Hamilton Cycle and its detailed proof
Lizhi Du · arXiv (Cornell University) · 2010
Popular algorithms to find a Hamilton circle in an undirected graph are generally based on the method developed by Posa. However, due to the deficiencies of Posa's method, such algorithms are only efficient for graphs that are either very dense or sparse but regular. This article introduces a method called Enlarged Rotation-Extension that modifies and extends Posa's method, overcoming its deficiencies. Based on this technique, our algorithm is polynomial and we give a detailed proof for it.