We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the n! Hamilton cycles in a complete directed graph on n + 1 vertices corresponds with each of the n! n-permutation matrices P, such that pu,i = 1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n + 1. A graph instance (G) is initially coded as exclusion set E, whose members are pairs of components of P, {pu,i, pv,i+1}, i = 1, n - 1, for each arc (u, v) not in
Swart,E R , Gismondi,S J , Swart,N R , Bell,C E and Lee,A . (2016). Deciding Graph non-Hamiltonicity via a Closure Algorithm. Journal of Algorithms and Computation, 48(1), 1-35. doi: 10.22059/jac.2016.7937
MLA
Swart,E R , , Gismondi,S J , , Swart,N R , , Bell,C E , and Lee,A . "Deciding Graph non-Hamiltonicity via a Closure Algorithm", Journal of Algorithms and Computation, 48, 1, 2016, 1-35. doi: 10.22059/jac.2016.7937
HARVARD
Swart E R, Gismondi S J, Swart N R, Bell C E, Lee A. (2016). 'Deciding Graph non-Hamiltonicity via a Closure Algorithm', Journal of Algorithms and Computation, 48(1), pp. 1-35. doi: 10.22059/jac.2016.7937
CHICAGO
E R Swart, S J Gismondi, N R Swart, C E Bell and A Lee, "Deciding Graph non-Hamiltonicity via a Closure Algorithm," Journal of Algorithms and Computation, 48 1 (2016): 1-35, doi: 10.22059/jac.2016.7937
VANCOUVER
Swart E R, Gismondi S J, Swart N R, Bell C E, Lee A. Deciding Graph non-Hamiltonicity via a Closure Algorithm. J. Algo. Comp.. 2016;48(1):1-35. doi: 10.22059/jac.2016.7937
