Hamiltonian path, routing, broadcasting algorithms for connected square network graphs

Abstract

Connected Square Network Graphs (CSNG) in the study of Selcuk (2022) and Selcuk and Tankul (2022) is reconsidered in this paper. Although (CSNG) is a 2-dimensional mesh structure, the most important feature of this graph is that it is a hypercube variant. For this reason, this study focuses on development algorithms that find solutions to various problems for (CSNG) with the help of hypercube. Firstly, an efficient algorithm that finds the Hamiltonian path is given. Further, two different algorithms that perform the mapping of labels in graph and the unicast routing are given. Furthermore, the parallel process for mapping and unicast routing is discussed. Finally, guidelines are given for broadcasting algorithms.

Keywords

• Meshes
• Hamiltonian path
• Routing
• Broadcasting