An innovative method for the detection of Hamiltonian cycles in Hypercubes

Year 2022, , 103 - 110, 07.12.2022

Fatih Okumuş , Ahmet Karadoğan

https://doi.org/10.53070/bbd.1199578

Abstract

The Hamilton cycle problem (HCP) is a well-known NP-hard problem for a given graph. In graphs, finding a path that starts from the first node, visits each node once, and stops at the first node again is the primary goal of HCP. In the resulting diagram, a complete cycle is produced as a result. Because of their regular structure and various edge connections, hypercubes are one of the preferred topologies for parallel machines and are also Hamiltonian graphs. Establishing the perfect match between the nodes requires the creation of the Hamilton diagram in hypercubes. This article proposes an original method that finds the Hamiltonian cycle of the Hypercube connected graph and the optimal way to derive this cycle. The proposed method primarily focuses on obtaining the basic cut-sets for the edges. Basic cut-sets are calculated by constructing Kmax and Kmin trees, which is an efficient spanning tree technique. At the end of the basic cut-set process on these two trees, the number of cuts for each edge is obtained. Then, a path is traced from the high priority node on the edge with the highest number of cuts to the lower degree node. All nodes are navigated with this method, provided that they do not come to the same node again. As a result, a Hamiltonian path is created between each node. Experimental studies with the proposed algorithm produced successful results and obtained a Hamiltonian cycle for all Hypercubes.

Keywords

Graphs, Hypercube, Hamiltonian cycle, Hamiltonian path, NP-hard problems

Hiperküplerde Hamilton çevriminin tespiti için yenilikçi bir yöntem

Abstract

Hamilton döngüsü problemi (HCP), belirli bir çizge için iyi bilinen bir NP-zor sorunudur. Çizgelerde, ilk düğümden başlayan, her düğümü bir kez ziyaret eden ve tekrar ilk düğümde duran bir yol bulmak, HCP'nin birincil amacıdır. Oluşan diyagramda sonuç olarak tam bir döngü üretilir. Düzenli yapısı ve çeşitli kenar bağlantılarından dolayı hiperküpler, paralel makineler için tercih edilen topolojilerden biridir ve aynı zamanda Hamiltonyen çizgelerdir. Düğümler arasında ideal eşleşmenin kurulması, hiperküplerde Hamilton diyagramının oluşturulmasını gerektirir. Bu makalede, Hiperküp bağlı çizgesinin Hamilton çevrimini ve bu çevrimi elde etmek için en uygun yolu bulan özgün bir yöntem önerilmektedir. Önerilen yöntem öncelikli olarak kenarlar için temel kesme kümelerini elde etmeye odaklanır. Temel kesme kümeleri etkili bir kapsam ağacı tekniği olan Kmax ve Kmin ağaçları oluşturularak hesaplanır. Bu iki ağaç üzerinde yapılan temel kesme işlemi sonunda her bir kenar için kesme sayısı elde edilir. Ardından, en yüksek kesme sayısına sahip kenardaki yüksek öncelikli düğümden düşük dereceli düğüme doğru bir yol takip edilir. Aynı düğüme tekrar gelmemek kaydıyla tüm düğümler bu yöntemle dolaşılır. Sonuç olarak her düğüm arasında bir Hamilton yolu oluşturulur. Önerilen algoritma ile yapılan deneysel çalışmalarda başarılı sonuçlar üretilmiş ve tüm Hiperküpler için bir Hamilton çevrimi elde etmiştir.

Keywords

Çizgeler, Hiperküp, Hamilton çevrimi, Hamilton yolu, NP-zor problemler

References

• M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. USA: W. H. Freeman & Co., 1990.
• Karp, R. M. Reducibility Among Combinatorial Problems, In Complexity of Computer Computations (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum Press, pp. 85-103, 1972.
• Boals, A.J., Gupta, A.K., Sherwani, N.A., Incomplete hypercubes: Algorithms and embeddings, The Journal of Supercomputing Vol:8, pp:263-294, 1994.
• O. Ore, “Hamilton-connected graphs,” J Math Pure Appl, vol. 42, pp. 21–27, 1963.
• J. S. Sartakhti, S. Jalili, and A. G. Rudi, “A new light-based solution to the Hamiltonian path problem,” Future Gener. Comput. Syst., vol. 29, no. 2, pp. 520–527, Feb. 2013, doi: 10.1016/j.future.2012.07.008.
• F. Keshavarz-Kohjerdi and A. Bagheri, “A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole,” Theor. Comput. Sci., vol. 690, pp. 26–58, Aug. 2017, doi: 10.1016/j.tcs.2017.05.031.
• J. Dybizbański and A. Szepietowski, “Hamiltonian cycles and paths in hypercubes with disjoint faulty edges,” Inf. Process. Lett., vol. 172, p. 106157, Dec. 2021, doi: 10.1016/j.ipl.2021.106157.
• DeBiasio, L., Martin, R.R., Molla, T.,Powers of Hamiltonian cycles in multipartite graphs, Discrete Mathematics, Vol:345, 112747, 2022.
• Agueda, R., Borozan, V., Diaz, R., Manoussakis, Y., Montero, L.,Proper Hamiltonian cycles in edge colored multigraphs, Discrete Mathematics, Vol:340, pp:1897-1902, 2017.
• Sivaraman, V., Zaslavsky, T., Two Hamiltonian cycles, Discrete Mathematics, Vol:345, 112797, 2022.
• Liu, H., Hu, X., Gao, S.,Hamiltonian cycles and paths in faulty twisted hypercubes, Discrete Applied Mathemaitics, Vol:257, pp:243-249, 2019.
• Liu, X., Wang, Z., Yu, X., Counting Hamiltonian cycles in planar triangulations, Journal of Combinatorial Theory, series B, Vol:155, pp:256-277, 2022.
• A. Karci, “New Algorithms for Minimum Dominating Set in Any Graphs,” 2020.
• A. Karci, “Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory,” Comput. Sci., vol. 5, no. 2, pp. 137–143, 2020.
• A. Karci, “Efficient Algorithms for Determining the Maximum Independent Sets in Graphs,” Comput. Sci., vol. 5, no. 2, pp. 144–149, 2020.
• A. Karci and Ş. Karci, “Determination of effective nodes in graphs,” Int. J. Adv. Comput. Eng. Netw., vol. ISSN, no. 8, pp. 2321–2063, 2020.
• Ş. KARCI, A. ARI, and A. KARCİ, “Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma,” Gazi Üniversitesi Mühendis.-Mimar. Fakültesi Derg., Oct. 2021, doi: 10.17341/gazimmfd.902093.