A fast algorithm for finding Hamilton cycles
Andrew. Chalaturnyk · Mspace (University of Manitoba) · 2008
This thesis is concerned with an algorithmic study of the Hamilton cycle problem.Determining if a graph is Hamiitonian is well known to be an NP-Complete problem, so a single most efficient algorithm is not known.Improvements to the understanding of any single NP-Complete problem may also be of interest to other l/P-Complete problems.However, it is an important problem and creating an algorithm which is efficient for many families of graphs is desirable.The majority of the work described within starts with an exhaustive backtracking search, called the N4ulti-Path method and explores two main areas: r Creating an algorithm based upon the method which is both efficient in time and memory when implemented in code.o Developing a pruning condition based upon separating sets that may be found during the execution of the method in order to maximi ze the amount of pruning possible. Both of these areas represent a significant evolution of previous work done withthe method.The resulting algorithm is extremely fast and requires only O(n -l e) space in memory, where n is the number of vertices and e is the number of edges.Additionally a class of graphs based on the Meredith graph is described.These graphs have a property which significantly affects the performance of the multi-path method.The insights that follow from this property lead to a reduction technique that further improves the algorithm in a significant way when determining if graphs Abstract are non-Hamiltonian.Further directions for study along the lines pursued by these insights is discussed.Testing of the algorithm is performed on a family of graphs known as knight's move graphs, which are known to be difficult for algorithms dealing with Hamilton cycles.