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., & Lee, A. (2016). Deciding Graph non-Hamiltonicity via a Closure Algorithm. Journal of Algorithms and Computation, 48(1), 1-35. https://doi.org/10.22059/jac.2016.7937
MLA
Swart, E. R., Gismondi, S. J., Swart, N. R., Bell, C. E., & 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 & 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
