International Journal of Mathematics and Mathematical Sciences
Volume 26 (2001), Issue 11, Pages 679-684
doi:10.1155/S0161171201004598
A logical model of HCP
Department of Information System, Vinnitsa Institute of Regional Economics and Management, Keletskaya Street, 60, Apt. 22, Vinnitsa 21021, Ukraine
Received 9 August 1999; Revised 19 October 1999
Copyright © 2001 Anatoly D. Plotnikov. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
For an arbitrary undirected graph G, we are designing a logical model for the Hamiltonian Cycle Problem (HCP), using tools of Boolean algebra only. The obtained model is a logic formulation of the conditions for the existence of the Hamiltonian cycle, and uses m Boolean variables, where m is the number of the edges of a graph. This Boolean expression is true if and only if an initial graph is Hamiltonian. In general, the obtained Boolean expression may have an exponential length (the number of Boolean literals) and may be used for construction of the solution algorithm.