Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suf...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2021-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1469 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850025676718997504 |
|---|---|
| author | Alexander V. Korostil Andrei V. Nikolaev |
| author_facet | Alexander V. Korostil Andrei V. Nikolaev |
| author_sort | Alexander V. Korostil |
| collection | DOAJ |
| description | We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist. |
| format | Article |
| id | doaj-art-c36e92c1c3b74bbfb41f63fec976ba4e |
| institution | DOAJ |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2021-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-c36e92c1c3b74bbfb41f63fec976ba4e2025-08-20T03:00:45ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172021-03-0128162110.18255/1818-1015-2021-1-6-211119Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular MultigraphAlexander V. Korostil0Andrei V. Nikolaev1P. G. Demidov Yaroslavl State UniversityP. G. Demidov Yaroslavl State UniversityWe consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist.https://www.mais-journal.ru/jour/article/view/1469hamiltonian decompositiontraveling salesperson polytope1-skeletonvertex adjacencybacktracking |
| spellingShingle | Alexander V. Korostil Andrei V. Nikolaev Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph Моделирование и анализ информационных систем hamiltonian decomposition traveling salesperson polytope 1-skeleton vertex adjacency backtracking |
| title | Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph |
| title_full | Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph |
| title_fullStr | Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph |
| title_full_unstemmed | Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph |
| title_short | Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph |
| title_sort | backtracking algorithms for constructing the hamiltonian decomposition of a 4 regular multigraph |
| topic | hamiltonian decomposition traveling salesperson polytope 1-skeleton vertex adjacency backtracking |
| url | https://www.mais-journal.ru/jour/article/view/1469 |
| work_keys_str_mv | AT alexandervkorostil backtrackingalgorithmsforconstructingthehamiltoniandecompositionofa4regularmultigraph AT andreivnikolaev backtrackingalgorithmsforconstructingthehamiltoniandecompositionofa4regularmultigraph |