Main content

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

Show simple item record

dc.contributor.advisor Steve, Gismondi Lee, Adrian 2017-09-14T20:55:15Z 2017-09-14T20:55:15Z 2017-09-13 2017-08-29 2017-09-14
dc.description.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. en_US
dc.language.iso en en_US
dc.rights Attribution-NonCommercial-NoDerivs 2.5 Canada *
dc.rights.uri *
dc.subject algorithms en_US
dc.subject perfect matching en_US
dc.subject co-NP complete en_US
dc.subject Hamilton cycles en_US
dc.subject graph theory en_US
dc.subject polynomial time en_US
dc.subject Hamilton cycle decision problem en_US
dc.title Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks en_US
dc.type Thesis en_US Mathematics and Statistics en_US Master of Science en_US Department of Mathematics and Statistics en_US
dc.rights.license 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 simple 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