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

Events Archive