Main content

Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks

Show full item record

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.


Files in this item

Files Size Format View
Lee_Adrian_201709_Msc.pdf 22.31Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Attribution-NonCommercial-NoDerivs 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 2.5 Canada