Çizgelerde Hamilton Çevrimi ve Yolunun Tespiti İçin Kenar Etkinliğine Dayalı Yeni Bir Algoritma

Öz

Bir çizgede tüm düğümleri birbirine bağlayan Hamilton çevrimi ve Hamilton yolunun varlığını araştırmak NP-tam bir problemdir. Bu makalede, kenar ağırlıkları olmayan keyfi bir çizgede Hamilton çevrimini oluşturmak için E2 Algoritması önerilmektedir. Öncelikle, temel kesitleri elde etmek amacıyla özel örten ağaçlar olan Kmax ve Kmin oluşturulmaktadır. Daha sonra, kenar etkinliğini belirlemek için her bir kenarın toplam temel kesit sayısı elde edilmektedir. Ardından, en etkin kenar üzerindeki en yüksek dereceli düğümden başlayarak önceliği belirleyen bir yöntemle tüm düğümler dolaşılmaktadır. Böylece, açgözlü geçiş başarılı olduğunda, tüm düğümler arasında bir Hamilton döngüsü veya yol oluşturulur. E² geri izleme içermeyen deterministik bir açgözlü algoritma olduğundan, her Hamilton grafiğinde bir Hamilton döngüsü bulmayı garanti etmez; ancak her zaman polinom zamanında sonlanır. Bu çalışmada, Hamilton çevrimini elde etmek için bu yöntemler ilk kez kullanılmaktadır. Ayrıca, üstel algoritma karmaşıklığının ortaya çıkmasını önlemek amacıyla nesne yönelimli bir yapı sunulmaktadır. Son olarak, yöntemin doğruluğunu göstermek için bazı genel çizgelerin önerilen yöntem kullanılarak Hamiltonyen olup olmadığı gösterilmektedir.

Anahtar Kelimeler

• Çizgeler
• Hamilton çevrimi
• Hamilton yolu
• NP-tam problemler

A Novel Edge-Efficiency-Based Algorithm for Hamiltonian Cycle and Path Detection in Graphs

Öz

Searching for the existence of a Hamiltonian cycle and path connecting all nodes in a graph is an NP-complete problem. This article proposes the E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights. The Kmax and Kmin that are particular spanning trees are generated first to obtain the fundamental cuts. Then, each edge's total number in the fundamental cuts is obtained to state edge efficiency. Next, all nodes are navigated with a method that determines priority, starting with the highest degree node at the most efficient edge. Thus, when the greedy traversal succeeds, a Hamiltonian cycle or path is constructed between all nodes. Since E² is a deterministic greedy algorithm without backtracking, it does not guarantee finding a Hamiltonian cycle in every Hamiltonian graph; however, it always terminates in polynomial time. These methods are used for the first time to obtain the Hamiltonian cycle in this study. In addition, we present an object-oriented construction to avoid getting exponential algorithm complexity. Finally, to prove the correctness of the method, we show whether some general graphs are Hamiltonian using the proposed method.

Anahtar Kelimeler

• Graphs
• Hamiltonian cycle
• Hamiltonian path
• NP-complete problems

Kaynakça

1. Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. USA: W. H. Freeman & Co., 1990.
2. Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, editors. Complexity of Computer Computations. New York: Plenum Press, 1972. pp. 85-103.
3. Ore O. Hamilton-connected graphs. J Math Pure Appl 1963; 42: 21-27.
4. Sartakhti JS, Jalili S, Rudi AG. A new light-based solution to the Hamiltonian path problem. Future Gener Comput Syst 2013; 29(2): 520-527.
5. Keshavarz-Kohjerdi F, Bagheri A. A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole. Theor Comput Sci 2017; 690: 26-58.
6. Dybizbański J, Szepietowski A. Hamiltonian cycles and paths in hypercubes with disjoint faulty edges. Inf Process Lett 2021; 172: 106157.
7. DeBiasio L, Spanier N. On Hamiltonian cycles in balanced k-partite graphs. Discrete Math 2021; 344: 112583.
8. DeBiasio L, Martin RR, Molla T. Powers of Hamiltonian cycles in multipartite graphs. Discrete Math 2022; 345: 112747.

9. Agueda R, Borozan V, Diaz R, Manoussakis Y, Montero L. Proper Hamiltonian cycles in edge colored multigraphs. Discrete Math 2017; 340: 1897-1902.
10. Sivaraman V, Zaslavsky T. Two Hamiltonian cycles. Discrete Math 2022; 345: 112797.
11. Liu H, Hu X, Gao S. Hamiltonian cycles and paths in faulty twisted hypercubes. Discrete Appl Math 2019; 257: 243-249.
12. Hell P, Nishiyama H, Stacho L. Hamiltonian cycles in covering graphs of trees. Discrete Appl Math 2020; 282: 271-281.
13. Liu X, Wang Z, Yu X. Counting Hamiltonian cycles in planar triangulations. J Combin Theory Ser B 2022; 155: 256-277.
14. Lu H, Wu T. Edge-disjoint Hamiltonian cycles of balanced hypercubes. Inf Process Lett 2019; 144: 25-30.
15. Liu JJ, Wang YL. Hamiltonian cycles in hypercubes with faulty edges. Inf Sci 2014; 256: 225-233.
16. T. Anuradha, T. L. Surekha, P. Nuthakki, B. Domathoti, G. Ghorai, F. A. Shami, and M. T. Rahim. Graph theory algorithms of Hamiltonian cycle from quasi-spanning tree and domination based on Vizing conjecture. Journal of Mathematics, pp. 1–7, 2022, doi: 10.1155/2022/1618498.
17. Biton N, Levi R, Medina M. Distributed CONGEST algorithm for finding Hamiltonian paths in Dirac graphs and generalizations. arXiv preprint 2023; arXiv:2302.00742.
18. M. Murua, D. Galar, R. Santana. Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm. Journal of Computational Science 2022; 61: 101618. doi: 10.1016/j.jocs.2022.101578
19. Karci A. New Algorithms for Minimum Dominating Set in Any Graphs. Journal of Computer Science 2020a; 5: 92-70.
20. Karci A. Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory. Journal of Computer Science 2020b; 5: 137-143.
21. Karci A. Efficient Algorithms for Determining the Maximum Independent Sets in Graphs. Journal of Computer Science 2020c; 5: 144-149.
22. Karci A, Karci Ş. Determination of effective nodes in graphs. In: International Conference on Science, Engineering and Technology; 2020; Mecca, Saudi Arabia. pp. 127-134.
23. Karci Ş, Ari A, Karci A. Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma. Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi 2021. doi: 10.17341/gazimmfd.902093.
24. Boals, A.J., Gupta, A.K. & Sherwani, N.A. Incomplete hypercubes: Algorithms and embeddings. J Supercomput 8, 263–294 (1994). https://doi.org/10.1007/BF01204731
25. Smaili F. A hybrid genetic-simulated annealing algorithm for multiple travelling salesman problems. Decision Science Letters 2024; 13: 1–14. doi: 10.5267/j.dsl.2024.4.001
26. Cheng J, et al. Dynamic path optimization based on improved ant colony algorithm. Journal of Advanced Transportation 2023; 2023: 7651100. doi: 10.1155/2023/7651100
27. Clares B, Roura S. Deterministic "Snakes and Ladders" heuristic for the Hamiltonian cycle problem. arXiv preprint 2019; arXiv:1902.10337.