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. doi: 10.22059/jac.2016.7937
MLA
E. R. Swart; Stephen 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
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
VANCOUVER
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, 2016; 48(1): 1-35. doi: 10.22059/jac.2016.7937
)