Hybrid Approach for Discovering k-Hamiltonian Paths in a Torus-Enhanced Butterfly Interconnected Network
Abstract
The significance of interconnection networks extends beyond the semiconductor industry, becoming integral to industrial engineering, particularly in the era of the Internet of Things (IoT). Both sectors share a strategic emphasis on developing sophisticated networks to enhance performance and scalability. Techniques such as Cartesian product fusion have led to the development of novel interconnected networks, addressing the demand for high-speed communication. The novel network topology, including the Torus-Enhanced Butterfly (TREB) network, is developed by the Cartesian product of the Torus (TR) and Enhanced Butterfly (EB) networks and holds unexplored aspects, particularly concerning the existence of Hamiltonian paths. The objective of this study is to devise a methodology for identifying k-Hamiltonian paths in an extensive TREB network. Contributions include theoretical and algorithmic proofs of Hamiltonian path existence using a hybrid approach. This approach divides the large TREB network graph into four EB subgraphs, and from each subgraph, all Hamiltonian paths are sought using the brute force method as a subsolution. Next, a dynamic programming-based algorithm is used to connect the Hamiltonian paths in these four subgraphs into a complete Hamiltonian path in the TREB network. The experiments reveal several properties of the TREB network that can only be derived through algorithmic approaches. These include the exact number of paths, which can be found from a valid permutation arrangement of the EB subgraphs, reaching approximately one billion paths, and the sequence of nodes forming Hamiltonian pathways.
Keywords: Hamiltonian paths, torus network, butterfly network, interconnection network, exact algorithms.
Full Text:
PDFReferences
ADEBAYO AO, CHAUBEY M, & NUMBU LP. Industry 4.0: The Fourth Industrial Revolution and How It Relates to the Application of Internet of Things(IoT). Journal of Multidisciplinary Engineering Science Studies, 2019, 5(2): 2477-2482. http://dx.doi.org/10.13140/RG.2.2.13334.40008
SASIAIN J, SANZ A, ASTORGA J, & JACOB E. Towards Flexible Integration of 5G and IIoT Technologies in Industry 4.0: A Practical Use Case. Applied Sciences, 2020; 10(21): 7670. https://doi.org/10.3390/app10217670
AL FAISAL F, RAHMAN M M H, and INOGUCHI Y. An Extensive Power and Performance Analysis for High Dimensional Mesh and Torus Interconnection Networks. International Journal of Distributed Systems and Technologies 2023, 14(1): 1-19, https://doi.org/10.4018/IJDST.321208.
AHMAD K, and SETHI M. Review of Network on Chip Routing Algorithms. EAI Endorsed Transactions on Context-Aware Systems and Applications, 2020, 7(22): e5, https://doi.org/10.4108/eai.23-12-2020.167793.
REDDYV P, JENA S, & PRASAD V K. An Efficient Dynamic Parallel and Distributed Network with Hybrid Hyper Cube. International Journal of Advanced Trends in Computer Science and Engineering, 2020, 9(4): 5200-5205, https://doi.org/10.30534/ijatcse/2020/147942020.
KALEEM M, and BIN ISNIN I F. A Survey on Network on Chip Routing Algorithms Criteria. In Advances in Intelligent Systems and Computing, 2021, 1188: 455-466 https://doi.org/10.1007/978-981-15-6048-4_40.
DORAISAMY R, MOHARIR M, and ARUL R. Congestion aware and game based odd even adaptive routing in network on chip many-core architecture. Indonesian Journal of Electrical Engineering and Computer Science, 2022, 28(2): 962-972, https://doi.org/10.11591/ijeecs.v28.i2.pp962-972.
ABRAHAM J, and AROCKIARAJ M. Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path. Parallel Processing Leters., 2021, 31(1): 2150004, https://doi.org/10.1142/S0129626421500043.
AROCKIARAJ M, LIU J B, DELAILA J N, and SHALINI A J. On the optimal layout of balanced complete multipartite graphs into grids and tree related structures. Discrete Applied Mathematics, 2021, 288: 50-65, https://doi.org/10.1016/j.dam.2020.08.022.
LI F, WANG W, XU Z, and ZHAO H. Some results on the lexicographic product of vertex-transitive graphs. Applied Mathematics Letters, 2011, 24(11): 1924-1926, https://doi.org/10.1016/j.aml.2011.05.021.
ZHANG Z, XIAO W J, and WEI W H. Some properties of cartesian product of cayley graphs. Proceedings of the 2009 International Conference on Machine Learning and Cybernetics, 2009: 2153-2157. https://doi.org/10.1109/ICMLC.2009.5212231.
PISANSKI T, and TUCKER T W. Growth in products of graphs. Australasian Journal of Combinatorics, 2002, 26: 155-169
AMBULGEKAR S, MALEWADIKAR S, GARANDE R, and JOSHI B. Next Words Prediction Using Recurrent NeuralNetworks. ITM Web Conferences, 2021, 40: 03034, https://doi.org/10.1051/itmconf/20214003034.
LAI P L, and TSAI C H. Embedding of tori and grids into twisted cubes. Theoretical Computer Science, 2010, 411(40-42): 3763-3773, https://doi.org/10.1016/j.tcs.2010.06.029.
XUE S, DENG Q, LI P, and CHEN J. Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges. Discrete Applied Mathematics, 2023, 334: 68-80, https://doi.org/10.1016/j.dam.2023.02.016.
PARK J H. Torus-like graphs and their paired many-to-many disjoint path covers. Discrete Applied Mathematics, 2021, 289: 64-77, https://doi.org/10.1016/j.dam.2020.09.008.
SHVALB N, FRENKEL M, SHOVAL S, and BORMASHENKO E. Universe as a Graph (Ramsey Approach to Analysis of Physical Systems). World Journal of Physics, 2023, 01(01): 1-24, https://doi.org/10.56439/wjp/2023.1101.
LANEL G H J, PALLAGE H K, RATNAYAKE J K, et al. A survey on Hamiltonicity in Cayley graphs and digraphs on different groups. Discrete Mathematics, Algorithms and Applications, 2019, 11(5): 1930002, https://doi.org/10.1142/S1793830919300029.
GU H, XIE Q, WANG K, et al. X-torus: A variation of torus topology with lower diameter and larger bisection width. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2006: 149-157. https://doi.org/10.1007/11751649_16.
RAHMAN M M H, INOGUCHI Y, AL FAISAL F, and KUNDU M K. Symmetric and folded tori connected torus network. Journal of Networks, 2011, 6(1): 26-35, https://doi.org/10.4304/jnw.6.1.26-35.
LIU Y, HAN J, and DU H. A hypercube-based scalable interconnection network for massively parallel computing. Journal of Computers, 2008, 3: 58-65. https://doi.org/10.4304/jcp.3.10.58-65.
CAI Z, XIAO W, ZHANG Q, and LIU Y. Principle of Symmetry for Network Topology with Applications to Some Networks. Journal of Networks, 2010, 5(9): 994-1000, https://doi.org/10.4304/jnw.5.9.994-1000.
CURRAN S J, and GALLIAN J A. Hamiltonian cycles and paths in Cayley graphs and digraphs - A survey. Discrete Mathematics, 1996, 156(1-3): 1-18, https://doi.org/10.1016/0012-365X(95)00072-5.
WITTE D, and GALLIAN J A. A survey: Hamiltonian cycles in Cayley graphs. Discrete Mathematics, 1984, 51(3): 293-304, https://doi.org/10.1016/0012-365X(84)90010-4.
CHENG S, ZHONG W, ISAACS K E, and MUELLER K. Visualizing the Topology and Data Traffic of Multi-Dimensional Torus Interconnect Networks. IEEE Access, 2018, 6: 57191-57204, https://doi.org/10.1109/ACCESS.2018.2872344.
CHOPKAR P N, and GAIKWAD M A. Review of XY routing algorithm for 2D torus topology of NoC architecture. International Journal of Computer Applications Special Issue Recent Trends in Engineering Technologies, 2013, 1: 22-26.
KINI N G, KUMAR M S, and MRUTHYUNJAYA H S. Torus Embedded Hypercube Interconnection Network: A Comparative Study. International Journal of Computer Applications, 2010, 1(4): 32-35, https://doi.org/10.5120/106-217.
BHARDWAJ M. C2 Torus New Interconnection Network Topology Based on 2D Torus. American Journal of Networks and Communications, 2015, 4(3): 1-4, https://doi.org/10.11648/j.ajnc.s.2015040301.11.
KINI N G, KUMAR M S, and MRUTHYUNJAYA H S. A torus embedded hypercube scalable interconnection network for parallel architecture. Proceedings of the 2009 IEEE International Advance Computing Conference, 2009: 858-861. https://doi.org/10.1109/IADCC.2009.4809127.
GUZIDE O, and WAGH M D. Enhanced Butterfly: A Cayley Graph with Node Degree 5. Proceedings of the 20th International Conference on Parallel and Distributed Computing Systems, 2007: 224-229.
LATIFAH L, ERNASTUTI E, and KERAMI D. Embeddings on Torus-Butterfly Interconnection Network. International Journal of Applied Information Systems, 2012, 4(9): 39-41, https://doi.org/10.5120/ijais12-450817.
LATIFAH L, ERNASTUTI E, and KERAMI D. Structural Properties of Torus-Butterfly Interconnection Network. International Journal of Computer Applications, 2012, 46(16): 31-35.
UMA S, and MAHESWARI B. Some Properties of Cartesian Product Graphs of Cayley Graphs with Arithmetic Graphs. International Journal of Computer Applications, 2016, 138(3): 26-29, https://doi.org/10.5120/ijca2016908742.
ZHANG Z, and XIAO W. A new family of Cayley graph interconnection networks based on wreath product and its topological properties. Cluster Computing, 2011, 14(4): 483-490, https://doi.org/10.1007/s10586-011-0189-0.
ZHANG Z. Some Properties in Hexagonal Torus as Cayley Graph. Communications in Computer and Information Science, 2011, 135: 422-428. https://doi.org/10.1007/978-3-642-18134-4_68.
PANDEY A, and SINGH C. Application of Graph Theory in Real Life to Develop Routes. International Journal for Multidisciplinary Research, 2023, 5(2): 1-7, https://doi.org/10.36948/ijfmr.2023.v05i02.1886.
SINGH K, BEDI S K, and GAUR P. Identification of the most efficient algorithm to find hamiltonian path in practical conditions, Proceedings of the 10th International Conference on Cloud Computing, Data Science and Engineering, 2020: 38-44. https://doi.org/10.1109/Confluence47617.2020.9058283.
LERA-ROMERO G, MIRANDA BRONT J J, and SOULIGNAC F J. Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows. INFORMS Journal on Computing, 2022, 34(6): 3292-3308, https://doi.org/10.1287/ijoc.2022.1236.
LU Y, BENLIC U, and WU Q. A hybrid dynamic programming and memetic algorithm to the Traveling Salesman Problem with Hotel Selection. Computers & Operations Research, 2018, 90: 193-207, https://doi.org/10.1016/j.cor.2017.09.008.
BAIDOO E, and OPPONG S O. Solving the TSP using Traditional Computing Approach. International Journal of Computer Applications, 2016, 152(8): 13-19, https://doi.org/10.5120/ijca2016911906.
PETTERSSON V. H. Enumerating hamiltonian cycles. Electronic Journal Of Combinatorics, 2014, 21(4): 4.7, https://doi.org/10.37236/4510.
MASKOOKI A, and KALLIO M. A bi-criteria moving-target travelling salesman problem under uncertainty. European Journal of Operational Research, 2023, 309(1): 271-295, https://doi.org/10.1016/j.ejor.2023.01.009.
RIYAD W A, YEE S C P, THINAKARAN R A P, and SALAM Z A B A. Comparative evaluation of numerous optimization algorithms for compiling travel salesman problem. Journal of Advanced Research in Dynamical and Control Systems, 2020, 12(7 Special Issue): 877-883, https://doi.org/10.5373/JARDCS/V12SP7/20202178.
WAN Y, FENG C, WU K, and WANG J. Progressive Construction of k-identifiable Networks. Proceedings of the 30th International Symposium on Quality of Service, 2022: 1-10. https://doi.org/10.1109/IWQoS54832.2022.9812924.
CLAUSEN J. Branch and bound algorithms-principles and examples. Technical Report. Department of Computer Science, University of Copenhagen, 1999, 1-30, https://doi.org/10.1.1.5.7475.
CAHYANI C A M, and WIRADINATA T. Traveling Salesman Problem Multi-destination Route Recommendation System Using Genetic Algorithm and Google Maps API. International Journal of Computer Applications, 2023, 185(18): 35-43, https://doi.org/10.5120/ijca2023922907.
PIRIM H, BAYRAKTAR E, and EKSIOGLU B. Tabu Search: A Comparative Study. in Tabu Search, 2008: 1-30. https://doi.org/10.5772/5637.
BAJEH A O. Optimization: A Comparative Study of Genetic and Tabu Search Algorithms. International Journal of Computer Applications, 2011, 31(5),
LIDBE A D, HAINEN A M, and JONES S L. Comparative study of simulated annealing, tabu search, and the genetic algorithm for calibration of the microsimulation model. Simulation, 2017, 93(1): 21-33, https://doi.org/10.1177/0037549716683028.
ADEWOLE, A. P. et al. A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem. International Journal of Applied Information Systems, 2012, 4: 6-12.
DUARTE A, LAGUNA M, and MARTÍ R. Tabu Search. in Metaheuristics for Business Analytics. EURO Advanced Tutorials on Operational Research, 2018: 85-103. https://doi.org/10.1007/978-3-319-68119-1_4.
AWAD F H, AL-KUBAISI A, and MAHMOOD M. Large-scale timetabling problems with adaptive tabu search. Journal of Intelligent Systems, 2022, 31(1): 168-176, https://doi.org/10.1515/jisys-2022-0003.
GUPTA D. Solving TSP Using Various Meta-Heuristic Algorithms, International Journal of Recent Contributions from Engineering, Science & IT, 2013, 1(2): 22-26. https://doi.org/10.3991/ijes.v1i2.3233.
O’REGAN G. Introduction to Algorithms. In Mathematical Foundations in Software Engineering. 2023: 69-84. https://doi.org/10.1007/978-3-031-26212-8_4.
Refbacks
- There are currently no refbacks.
