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...
Saved in:
| Main Author: | |
|---|---|
| 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!
|
| _version_ | 1832552871537672192 |
|---|---|
| author | Anatoly D. Plotnikov |
| author_facet | Anatoly D. Plotnikov |
| author_sort | Anatoly D. Plotnikov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a32eaf2fd6424cf0995fe89ea5d43811 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2001-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-a32eaf2fd6424cf0995fe89ea5d438112025-02-03T05:57:36ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252001-01-01261167968410.1155/S0161171201004598A logical model of HCPAnatoly D. Plotnikov0Department of Information System, Vinnitsa Institute of Regional Economics and Management, Keletskaya Street, 60, Apt. 22, Vinnitsa 21021, UkraineFor 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.http://dx.doi.org/10.1155/S0161171201004598 |
| spellingShingle | Anatoly D. Plotnikov A logical model of HCP International Journal of Mathematics and Mathematical Sciences |
| title | A logical model of HCP |
| title_full | A logical model of HCP |
| title_fullStr | A logical model of HCP |
| title_full_unstemmed | A logical model of HCP |
| title_short | A logical model of HCP |
| title_sort | logical model of hcp |
| url | http://dx.doi.org/10.1155/S0161171201004598 |
| work_keys_str_mv | AT anatolydplotnikov alogicalmodelofhcp AT anatolydplotnikov logicalmodelofhcp |