Hybrid Approach for Discovering k-Hamiltonian Paths in a Torus-Enhanced Butterfly Interconnected Network
Tubagus Mohammad Akhriza Latifah, Tubagus Mohammad Akhriza Latifah · Journal of Hunan University Natural Sciences · 2023
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. https://doi.org/10.55463/issn.1674-2974.50.12.14