MSc Math Defence: Investigating The Use of Perfect Matching in An Algorithm to Detect Non-Hamiltonicity of Snarks by Adrian Lee
Date and Time
Location
Summerlee Science Complex Room 2315
Details
CANDIDATE: ADRIAN LEE
ABTRACT
The Hamilton cycle decision problem is NP-complete. No efficient solution technique is known, and may or may not exist. In this thesis, the co-NP complete non-Hamilton cycle decision problem is investigated via the heuristic O(n8) weak closure algorithm, with modifications that exploit perfect matching to a greater extent. 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 bipartite matching algorithm. A small collection of snarks are tested and the algorithm correctly identifies these graphs as non-Hamiltonian.
Advisory Committee
- S. Gismondi (Advisor)
- H. Kunze
- J. Sawada
Examining Committee
- A. Willms, Chair
- S. Gismondi
- J. Sawada
- R. Pereria