A logical model of HCP

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 num...

Full description

Saved in:
Bibliographic Details
Main Author: Anatoly D. Plotnikov
Format: Article
Language:English
Published: Wiley 2001-01-01
Series:International Journal of Mathematics and Mathematical Sciences
Online Access:http://dx.doi.org/10.1155/S0161171201004598
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0161-1712
1687-0425