University of TehranJournal of Algorithms and Computation2476-277648120161128Deciding Graph non-Hamiltonicity via a Closure Algorithm1357937ENE. R.SwartKelowna, British Columbia, CanadaStephen J.GismondiUniversity of Guelph, CanadaN. R.SwartUniversity of British Columbia Okanagan, CanadaC. E.BellGuelph, Ontario, CanadaA.LeeUniversity of Guelph, CanadaJournal Article20160126We 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<sub>u</sub></em><sub>,<em>i</em></sub> = 1 if and only if the <em>i<sup>th</sup></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><sub><em>u</em>,<em>i</em></sub>, <em>p<sub>v</sub></em><sub>,<em>i</em>+1</sub>}, <em>i</em> = 1, <em>n</em> - 1, for each arc (<em>u</em>, <em>v</em>) not inhttps://jac.ut.ac.ir/article_7937_15545482e67a30452c97e86eb5b51fa9.pdf