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
dc.contributor.author Lee, Adrian
dc.date.accessioned 2017-09-14T20:55:15Z
dc.date.available 2017-09-14T20:55:15Z
dc.date.copyright 2017-09-13
dc.date.created 2017-08-29
dc.date.issued 2017-09-14
dc.identifier.uri http://hdl.handle.net/10214/11591
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 http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ *
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
dc.degree.programme Mathematics and Statistics en_US
dc.degree.name Master of Science en_US
dc.degree.department Department of Mathematics and Statistics en_US


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