A logical model of HCP

Anatoly D. Plotnikov

International Journal of Mathematics and Mathematical Sciences, 2001, vol. 26, 1-6

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.

Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/26/158787.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/26/158787.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:158787

DOI: 10.1155/S0161171201004598

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().