Document Type : Research Paper
Authors
1 Kelowna, British Columbia, Canada
2 University of Guelph, Canada
3 University of British Columbia Okanagan, Canada
4 Guelph, Ontario, Canada
Abstract
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
Keywords
)