The Weak Closure Algorithm
Speaker:
Adrian Lee, University of Guelph
Date and Time:
Saturday, June 10, 2017 - 11:30am to 11:55am
Abstract:
The Hamilton cycle decision problem is NP-Complete. No efficient solution technique is known, and may or may not exist. In this talk, the co-NP complete non-Hamilton cycle decision problem is investigated via the heuristic $O(n^8)$ Weak Closure Algorithm. Hamilton cycles are expressed as specially constructed block permutation matrices. The algorithm attempts to decide a graph's non-Hamiltonicity by checking for the non-existence of these permutation matrices using the matching algorithm. A small collection of simple 3-regular non-Hamiltonian graphs are tested and the algorithm correctly identifies these graphs as non-Hamiltonian.