Title:
|
Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks |
Author:
|
Lee, Adrian
|
Department:
|
Department of Mathematics and Statistics |
Program:
|
Mathematics and Statistics |
Advisor:
|
Steve, Gismondi |
Abstract:
|
The Hamilton cycle decision problem is NP-complete. No polynomial time algorithm that solves this problem 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(n^8) 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. |
URI:
|
http://hdl.handle.net/10214/11591
|
Date:
|
2017-09-13 |
Rights:
|
Attribution-NonCommercial-NoDerivs 2.5 Canada |
Terms of Use:
|
All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated. |