University of Tehran Journal of Algorithms and Computation 2476-2776 48 1 2016 11 28 Deciding Graph non-Hamiltonicity via a Closure Algorithm 1 35 7937 EN E. R. Swart Kelowna, British Columbia, Canada Stephen J. Gismondi University of Guelph, Canada N. R. Swart University of British Columbia Okanagan, Canada C. E. Bell Guelph, Ontario, Canada A. Lee University of Guelph, Canada Journal Article 2016 01 26 We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the <em>n</em>! Hamilton cycles in a complete directed graph on <em>n</em> + 1 vertices corresponds with each of the <em>n</em>! <em>n</em>-permutation matrices <em>P</em>, such that <em>p_u</em>_,<em>i</em> = 1 if and only if the <em>i^th</em> arc in a cycle enters vertex <em>u</em>, starting and ending at vertex <em>n</em> + 1. A graph instance (<em>G</em>) is initially coded as exclusion set <em>E</em>, whose members are pairs of components of <em>P</em>, {<em>p</em>_{<em>u</em>,<em>i</em>}, <em>p_v</em>_{,<em>i</em>+1}}, <em>i</em> = 1, <em>n</em> - 1, for each arc (<em>u</em>, <em>v</em>) not in https://jac.ut.ac.ir/article_7937_15545482e67a30452c97e86eb5b51fa9.pdf