# HAMILTON PATH, ROUTING AND BROADCASTING ALGORITHMS FOR CONNECTED SQUARE NETWORK GRAPHS

Burhan Selçuk, Ayşe Nur Altıntaş Tankül

<figure><img src="image_1.png" /></figure>

## To cite this version:

Burhan Selçuk, Ayşe Nur Altıntaş Tankül. HAMILTON PATH, ROUTING AND BROADCASTING ALGORITHMS FOR CONNECTED SQUARE NETWORK GRAPHS. 2022. hal-03872827

HAL Id: hal-03872827

https://hal.science/hal-03872827

Preprint submitted on 25 Nov 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# HAMILTON PATH, ROUTING AND BROADCASTING ALGORITHMS FOR CONNECTED SQUARE NETWORK GRAPHS

Burhan Selçuk¹ and Ayşe Nur A. Tankül¹

¹Computer Engineering Department, Karabük University, Karabük, Türkiye
bselcuk@karabuk.edu.tr, aysenuraltintas@karabuk.edu.tr

**ABSTRACT.** Connected Square Network Graphs (CSNG) in the study of Selcuk and Tankul [17,18] 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, the focus of this work is to develop algorithms that find solutions to various problems for (CSNG) with the help of hypercube's algorithms. Firstly, an efficient algorithm that finds the Hamiltonian path is given. Further, three different algorithms that perform the unicast routing are given. Furthermore, the parallel process for unicast routing is discussed. Finally, guidelines are given for broadcasting algorithms.

**Keyword:** Graph, Meshes, Hamilton path, Routing, Broadcasting

## 1. INTRODUCTION

Graphs appear in computer science as both a mathematical model and a data type. Hyper-cube graphs and their variants are frequently used in computer architecture. Hayes et al. used hypercube architecture to implement supercomputers [1], Nieminen et al. described pseudocubes using hypercubes, while pseudocubes have similar properties with hypercubes, [2], Chae et al. studied on general cubic graphs [3], Harary et al. presented comprehensive analysis of hypercube graphs [4] and Mao and Nicol studied on graphs named k-ary n-cubes [5], proposed a technique to define a variation of this topology and analyze it. Many researchers have studied hypercube and its variants and obtained their topological properties. For example Folded Hypercube is studied by El-Amawy and Latifi [8] investigates its properties, then Cahng and Chen [9] proposed the incrementally extensible folded hypercube as a new class and explained its properties while giving a simple routing algorithm. Crossed Cubes is another hypercube variant and its topological structure is studied by Dong et al. [10] embedded a 3D meshes family into it, Efe [11] gave an alternative way for parallel architectures using Crossed Cubes, and Lai et al. proposed a new dynamic programming algorithm to apply multidimensional torus in it [12]. Besides, there are many works about hierarchical networks. Abd-El-Barr and Al-Somani [13] reviewed and compared different type of hierarchical interconnection networks and their topological attributes, while Ghose
and Desai [14] introduce the hierarchical cubic network (HCN), a novel interconnection system for massive distributed memory multiprocessors. Hierarchical extended Fibonacci cubes HEFC1(n) is a new interconnection network structure proposed by Karci [15] and its properties are explained in the study. Karci also used Fibonacci series to suggest a new graphs which are hierarchically definable and sub-graphs of Hierarchic Cubic graphs [16]. Karci and Selcuk introduced new hypercube variants. These; Fractal Cubic Network Graph (FCNG) [6] using the fractal structures and Connected Cubic Network Graph [7] using hypercube shown in Fig 1.2, Fig 1.3. and Fig 1.4., and explain their properties while giving algorithms on these graphs. Connected Square Network Graphs which is introduced by Selcuk can be obtained using two different definitions, and this variant of hypercube is a Hamilton graph ( [17]). A new Hypercube-like Graph is introduced by Selcuk and Tankul which is another type of hypercube labeled with using gray code and the connectivity indexes are calculated ( [18]).

Motivated by [6,7], new algorithms for *CSNG* will be developed in this paper. Section 2 informs *CSNG*, divide and conquer method, dynamic programming, travelling salesman problem, routing problem and broadcasting problem. In section 3, a new Hamilton path algorithm is given with the help of a dynamic programming. Further, routing algorithms are also given and the parallel process for these algorithms are discussed in section 4. Finally, broadcasting algorithms are given for *CSNG* with the help of broadcasting algorithms for hypercube.

## 2. PRELIMINARIES

Rest of the study, let $u$ and $v$ be vertices in a graph $G$. $G$ is considered to be *CCNG* with vertex set $V(G)$ and edge set $E(G)$, $deg(u)$ is the degree of vertex $u \in V(G)$. "||" indicates the concatenation of two strings. The Hamming distance is $\sum_{i=0}^{n-1}(a_i \oplus b_i)$ since $\oplus$ is bit-wise XOR operation. $S(2)$ is denoted a square in 2D space. The 2D coordinate system is given below:

<figure><img src="image_3.png" /><figcaption>FIGURE 1. 2D coordinate space</figcaption></figure>

**Definition 2.1. (CSNG):** Let $CSNG(0, 0) = S(2)$. $CSNG(k, m)$ can be defined in two steps.

*Case I. Construction in one direction*

(i) Suppose $\sum_{i=0}^{m} 2^i$ squares with common two nodes (an edge) are connected along the y-axis. This graph will be called a $CSNG(0, m)$. For example, the mesh structures given in Figure 2-(a) and Figure 3 are $CSNG(0, 1)$ and $CSNG(0, 2)$, respectively.

(ii) Suppose $\sum_{i=0}^{k}$ squares with common two nodes (an edge) are connected along the x-axis. This graph will be called a $CSNG(k, 0)$. For example, the mesh structure given in Figure 2-(b) is $CSNG(1, 0)$.
<figure><img src="image_4.png" /><figcaption>FIGURE 2. a. $CSNG(0,1)$, b. $CSNG(1,0)$, respectively</figcaption></figure>

Case II. Construction in two directions

(i) Suppose $\sum_{i=0}^{m} 2^i CSNG(k, 0)$s with a common edge (right and left edges) are connected along the y-axis. This graph will be called a $CSNG(k, m)$.

(ii) Suppose $\sum_{i=0}^{k} 2^i CSNG(0, m)$s with a common edge (lower and upper edges) are connected along the x-axis. This graph will be called a $CSNG(k, m)$. For example, the mesh structure given in Figure 4 is $CSNG(1, 2)$.

<figure><img src="image_5.png" /><figcaption>FIGURE 3. $CSNG(0,2)$: Case 1-(i) of Def. 1.1</figcaption></figure>

2.1. Divide and Conquer. There are different methods of designing algorithms. One approach is the divide-and-conquer algorithm, which is an algorithm as the name suggests, dividing the problem into sub-problems to make it easier to solve the original problem. It solves sub-problems that are like a smaller version of the original problem and combines the solutions of the sub-problems to form the solution of the original problem ([19]). The divide-and-conquer paradigm increases program modularity, often leading to simple and efficient algorithms. It has therefore
<figure><img src="image_6.png" /><figcaption>FIGURE 4. CSNG(1, 2): Case 2-(ii) of Def. 1.1</figcaption></figure>

proven to be a powerful tool for sequential algorithm designers. The structure of divide-and-conquer algorithms is recursive. Divided sub-problems are generally smaller size of the original problem, so the original problem calls itself recursively to solve the sub-problems. The divide and conquer method has three steps at each recursive level;

* Divide the problem into similar sub-problems,

* Conquer these sub-problems with using recursive method to solve,

* Combine the solutions by solving the sub-problems into the solution that will be the original problem solution.

Divide and conquer parallel algorithm design plays an even more important role. Since the sub-problems created in the first step are usually independent, they can be solved in parallel. Usually the sub-problems are solved recursively, resulting in more sub-problems to be solved in parallel in the next dividing step. However, it should be noted that in order to obtain a highly parallel algorithm, the division and merge steps of divide and conquer must be parallelized. It is quite common in parallel algorithms to solve the original problem in parallel by dividing it into as many sub-problems as possible. For the Parallel Divide and Conquer example, consider the sequential Merge Sort algorithm. Merge sort takes n elements and returns them in order. This algorithm works by dividing an array of n elements into two parts, each dividing array recursively sorted, and combined the sorted semi-arrays.

## 2.2. Dynamic Programming.
Dynamic programming is generally applied to the most of the optimization problems where a series of choices must be made to reach an optimal solution. Same sub-problems often arise while making choices. Dynamic programming is an algorithm design methodology much the same as divide and conquer, splitting problem into similar sub-problems and solving them recursively ( [19]). Dynamic programming is used when the partitioned sub-problems of original problem are repeated and not independent. Each sub-problem is solved just
once by the algorithm and then the solution of the problem is saved in a table. Because it saves
the solution of sub-problems, it reduces the cost of code by eliminating the need to recalculate the
same operations. The structure of dynamic programming is also recursive, method calls itself for
sub-problems of main problem, and solves it if the sub-problem is encountered for the first time.
Dynamic programming has four steps in development process ([19]);

* Characterization of the optimal solution structure,

• Iterative definition of the value for an optimal solution,

* Calculation of the value for an optimal solution from the bottom up,

* Build an optimal solution from the calculated information.

First three steps are the basic steps of a dynamic programming. If we only need the value
of the optimal solution, it will be sufficient to use only the first three steps, last step can be
skipped. Dynamic programming have been using for computer science, mathematics, economics
and bio-informatics.

2.3. **Travelling Salesman Problem (Hamilton path).** Traveling Salesman Problem is one of the NP-hard optimization problem that means it has a large search space for the solution, so running time is not polynomial ( [20]). In the Traveling Salesman Problem (TSP), the goal is to find the shortest tour a seller takes, starting from the city he is in and returning to the city where he started after stopping by each city only once. We assume that there is a road between any two cities and that we know the length of that road. It is easy to understand but difficult to solve. TSP, in the language of graph theory, is to find the shortest Hamiltonian cycle on a (plain) graph where cities are represented by the vertex and roads by the edges between the vertices.

The Hamiltonian path is named after 19th century mathematician William Hamilton which
passes through each node on a graph only once. If a Hamilton path ends where it started,
completes a full cycle (if it is possible to go from the last node on the path to the first node),
these paths is called the Hamiltonian cycle. A graph containing a Hamiltonian cycle also includes
a Hamiltonian path, but the reverse is not always true. The graphs have Hamiltonian cycle are
called Hamiltonian graphs.

Nowadays, TSP is used in many other fields. Microchip manufacturing, drilling in printed circuit boards, vehicle routing, packet routing in GSM are some of its applications.

2.4. **Routing.** Routing is the process of finding the closest and potential paths between nodes in a network topology. According to purpose and complexity, there are two main types of routing problems ( [21]). The shortest path is the main issue in the first category of path finding prob- lems. Compared to other routing problems, these problems are rather simple. Tour construction problems are the second group. It is more complex than the first category problems of building an entire tour within a given network. As an example, real distance and geographical information system (GIS) are used to solve real world problems represented as a network.

Path Finding Problems are actually Shortest Path Problems (SPP) find the minimum total cost (time, distance, expense) between two nodes. Single Source Shortest Path is for finding a path
between source and destination vertices. There are different algorithms for these problems. All Pair Shortest Path to find paths between all vertices pairs in the network. Tour construction problems can be divided into three classes: Travel Salesman Problem (TSP) is the first one and most widely known, Vehicle Routing Problem (VRP) is the generalized version of TSP with many salesmans, and lastly Bus Routing Problem (BRP) is another version of TSP with route balancing, may have time window constraints and busses can have same or different capacities.

2.5. **Broadcasting.** In computer networks, casting refers to sending data over the network used for communication between hosts. Types of casting used in networking are as follows:

* Unicast transmission is one-to-one transmission used to send data from one sender to one receiver.

* Broadcast transmission is to-all transmission that sending data from one or more hosts to all hosts in the network.

* Multicast transmission is one-to-many transmission where there is a single source that is sending data to the specific group in the network.

The broadcasting process occurs with sequential data transmissions between pairs of nodes. Broadcast communication is often required in image processing, parallel implementation of algorithms or scientific computations, spread large data arrays among system nodes and to carry out various data processing activities. There are two way for broadcasting the message over the network ([22]). First one is one-to-all broadcasting, transmission of the identical message from originating source to all nodes over the network. The m-size data that needs to be published is initially only available in the source node. At the end of the procedure there are n (number of nodes in the network) copies of the initial data, one at each node. All-to-all is the other type of broadcasting also called total exchange or gossip. In this broadcasting, each node delivers a message to every other node in the network. All nodes simultaneously start a broadcast in an all-to-all broadcast, which is a generalization of one-to-all broadcast. One node sends the same message to all nodes, however different nodes may broadcast different messages. Broadcasting algorithms are existed for linear array, mesh, and hypercube topologies. The most known and used broadcast algorithms are Recursive Doubling, Network Partitioning and Extending Dominating Node algorithms ([23]).

### 3. HAMILTON PATH ALGORITHM

In this section, a new Hamiltonian path algorithm for CSNG is introduced. The dynamic programming method is used in recursive structures like the divide and conquer method. Since it calculates the sub problems once and stores this value in the table, it can offer better performance than the divide and conquer method. Thus, the dynamic programming method will be used in the following Algorithm 1. 1 bit change between labels of neighboring nodes is provided with the help of gray code in this algorithm.

**Example 3.1.** Firstly, it is assumed to be a Hamiltonian path for a square in 2D space;

$$00 \rightarrow 01 \rightarrow 11 \rightarrow 10.$$
Assume that initial node is 01001 on CSNG(3, 0) (or CSNG(2, 1), CSNG(1, 2), CSNG(0, 3)). In fact, 010 for the outer recursive structure and 01 for the inner recursive structure are chosen as the initial node. In order to obtain the Hamiltonian path for the inner recursive structure, the Hamiltonian path considered above must be shifted so that the starting node is 01 (See step 1 in Algorithm 1). A Hamiltonian path for the square will be named $H(0)$ and $inv_H(0)$ (reverse sorted of $H(0)$) are obtained as follows:

$$H(0) = 01 \rightarrow 11 \rightarrow 10 \rightarrow 00, inv_H(0) = 00 \rightarrow 10 \rightarrow 11 \rightarrow 01.$$

For the outer recursive structure (See step 2 in Algorithm 1), the last node is 0 on 010, and then the result of the first iteration;

$$ \begin{aligned} H(1) &= 0||H(0) \rightarrow 1||inv_H(0) \\ &= 001 \rightarrow 011 \rightarrow 010 \rightarrow 000 \rightarrow 100 \rightarrow 110 \rightarrow 111 \rightarrow 101, \end{aligned} $$

and

$$ \begin{aligned} inv_H(1) &= 1||H(0) \rightarrow 0||inv_H(0) \\ &= 101 \rightarrow 111 \rightarrow 110 \rightarrow 100 \rightarrow 000 \rightarrow 010 \rightarrow 011 \rightarrow 001. \end{aligned} $$

the middle node is 1 on 010, and then the result of the second iteration;

$$ \begin{aligned} H(2) &= 1||H(1) \rightarrow 0||inv_H(1) \\ &= 1001 \rightarrow 1011 \rightarrow 1010 \rightarrow 1000 \rightarrow 1100 \rightarrow 1110 \rightarrow 1111 \rightarrow 1101 \rightarrow \\ & \quad 0101 \rightarrow 0111 \rightarrow 0110 \rightarrow 0100 \rightarrow 0000 \rightarrow 0010 \rightarrow 0011 \rightarrow 0001, \end{aligned} $$

and

$$ \begin{aligned} inv_H(2) &= 0||H(1) \rightarrow 1||inv_H(1) \\ &= 0001 \rightarrow 0011 \rightarrow 0010 \rightarrow 0000 \rightarrow 0100 \rightarrow 0110 \rightarrow 0111 \rightarrow 0101 \rightarrow \\ & \quad 1101 \rightarrow 1111 \rightarrow 1110 \rightarrow 1100 \rightarrow 1000 \rightarrow 1010 \rightarrow 1011 \rightarrow 1001. \end{aligned} $$

Start from node 0 on 010, and then the result of the last iteration;

$$ \begin{aligned} H(3) &= 0||H(2) \rightarrow 1||inv_H(2) \\ &= 01001 \rightarrow 01011 \rightarrow 01010 \rightarrow 01000 \rightarrow 01100 \rightarrow 01110 \rightarrow 01111 \rightarrow 01101 \rightarrow \\ & \quad 00101 \rightarrow 00111 \rightarrow 00110 \rightarrow 00100 \rightarrow 00000 \rightarrow 00010 \rightarrow 00011 \rightarrow 00001 \rightarrow \\ & \quad 10001 \rightarrow 10011 \rightarrow 10010 \rightarrow 10000 \rightarrow 10100 \rightarrow 10110 \rightarrow 10111 \rightarrow 10101 \rightarrow \\ & \quad 11101 \rightarrow 11111 \rightarrow 11110 \rightarrow 11100 \rightarrow 11000 \rightarrow 11010 \rightarrow 11011 \rightarrow 11001. \end{aligned} $$

**Remark 3.2.** The Algorithm 1 finds Hamiltonian path for CSNG($k, m$) using dynamic programming. If this algorithm with divide and conquer were designed, two nested recursive structures
would have to be encountered. This would mean an increase in the complexity of the algorithm. The running time of the Algorithm 1 is $O(k+m)$.

$CSNG(k, m)$ has $2^{k+m+2}$ nodes. $CSNG(0, 0)$ is equivalent to the square and has $2^2$ nodes. Although $C(2, 0)$, $C(0, 2)$ and $C(1, 1)$ have the same number of nodes, they are not isomorphic graphs. However, a Hamiltonian path for these graphs that are not isomorphic due to the construction of the $CSNG(k, m)$ graph can be obtained in a similar way using the Algorithm 1.

## 4. COMMUNICATION ALGORITHMS

In this section, new unicast routing algorithms for $CSNG$ are introduced and hence one iterative and two recursive algorithms are given.

### 4.1. Unicast Routing Algorithms.
The nodes on the networks decide who will receive the message sent by various methods while communicating with other nodes. Some messages are directly sent to a node, some are intended to reach a specific set of nodes, and some reach all nodes in the same network.

If the message you will send to the network directly concerns a single node, and you already know the address of the node, you send the message using an algorithm designed as unicast. Thus, the network elements used in between perform the task of transmitting the message only to the specified node. Broadcast algorithms deliver the message to all nodes while multicast algorithms are used for communication within the group.

For $CSNG(k, m)$, unicast routing is similar with e-square routing is used for mesh networks. Between source $S$ and destination $D$ nodes, minimum distance is calculated by number of 1s in $S$ exclusive or ($\oplus$) $D$.

We can assume that the result of the $S \oplus D$ is the direction. Each node in the route can be calculated iteratively starting from least significant non zero bit of direction. From source to destination, next node is calculated by XOR operation between current node and a non zero bit of direction. Time complexity for this algorithm is $\Theta(k+m)$.

**Example 4.1.** Let $S : (Source) = 10101$ and $D : (Destination) = 00010$ be the two nodes selected from the label set of $CCNG(3, 0)$ (or $CCNG(2, 1)$, $CCNG(1, 2)$, $CCNG(0, 3)$). The classical method is to first determine how many bits are changed from $S$ to $D$. The effortless way to detect this is using XOR ($\oplus$) processing, namely $r = S \oplus D$. For this example, $r = 10101 \oplus 000100 = 10111$. It is understood from this binary number to reach $D$ from $S$, path will go through 4 nodes. This route is

$$S : (Source) = 10101 \rightarrow 00101 \rightarrow 00001 \rightarrow 00011 \rightarrow 00010 = D : (Destination).$$

**Remark 4.2.** The Algorithm 2 finds unicast routing Hamiltonian path for $CSNG(k, m)$ using similar approach for unicast routing algorithm of Hypercube in $3D$ (see [22]). the complexity of the Algorithm 2 is $\Theta(L)$ where $L$ equal to $(k+m+2)$.
**Algorithm 1:** This algorithm calculate an alternative Hamilton path with CSNG(k, m) using dynamic programming process.

**Data:** k, m, initial_node and case: 1 or 2

**Result:** H: Hamilton path of CSNG(k, m)

1 begin

2 // Step 1: Alternative Hamilton path for square

3 if $k + m == 0$ then

4 if initial_node == 00 then

5 if case == 1 then
6 $H(0) = 00 \to 01 \to 11 \to 10, inv_H(0) = 10 \to 11 \to 01 \to 00$

7 if case == 2 then
8 $H(0) = 00 \to 10 \to 11 \to 01, inv_H(0) = 01 \to 11 \to 10 \to 00$

9 if initial_node == 01 then

10 if case == 1 then
11 $H(0) = 01 \to 11 \to 10 \to 00, inv_H(0) = 00 \to 10 \to 11 \to 01$

12 if case == 2 then
13 $H(0) = 01 \to 00 \to 10 \to 11, inv_H(0) = 11 \to 10 \to 00 \to 01$

14 if initial_node == 11 then

15 if case == 1 then
16 $H(0) = 11 \to 10 \to 00 \to 01, inv_H(0) = 01 \to 00 \to 10 \to 11$

17 if case == 2 then
18 $H(0) = 11 \to 01 \to 00 \to 10, inv_H(0) = 10 \to 00 \to 01 \to 11$

19 if initial_node == 10 then

20 if case == 1 then
21 $H(0) = 10 \to 00 \to 01 \to 11, inv_H(0) = 11 \to 01 \to 00 \to 10$

22 if case == 2 then
23 $H(0) = 10 \to 11 \to 01 \to 00, inv_H(0) = 00 \to 01 \to 11 \to 10$

24 // Step 2: A Hamilton path for CSNG(k, m)

25 for $i = 1$ to $k + m$ do

26 if initial_node($i + 2$) == 0' then
27 $H(i) = 0 || inv_H(i - 1) \to 1 || inv_H(i - 1), inv_H(i) = 1 || inv_H(i - 1) \to 0 || inv_H(i - 1)$

28 if initial_node($i + 2$) == 1' then
29 $H(i) = 1 || inv_H(i - 1) \to 0 || inv_H(i - 1), inv_H(i) = 0 || inv_H(i - 1) \to 1 || inv_H(i - 1)$

30 return H
**Algorithm 2:** This algorithm calculate unicast routing for connected square network graphs using similar approach Hypercube's unicast routing algorithm (iterative process).

**Data:** $k, m$ and $S$: source, $D$: destination, $MSG$: message, $r$: route

**Result:** $MSG$ message is transmitted from $S$ to $D$ using $r$

1 **begin**
2 &nbsp;&nbsp;&nbsp;&nbsp;$L = k + m + 2$ // length of source and destination nodes
3 &nbsp;&nbsp;&nbsp;&nbsp;$dir = S \oplus D$ // length of source and destination nodes
4 &nbsp;&nbsp;&nbsp;&nbsp;$r[0] = \text{Source}$
5 &nbsp;&nbsp;&nbsp;&nbsp;$j=1$
6 &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1$ **to** $L - 1$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $dir(i) == 1$ **then**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$r[j] = r[j - 1] \oplus 2^i$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$r[j] \leftarrow \text{MSG}$
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$j = j + 1$

**Algorithm 3:** This algorithm calculate unicast routing for $CSNG(k, m)$ using divide and conquer approach (recursive process).

**Data:** $S$ = source, $D$ = destination, $MSG$, $n$=size of $S$ and $D$

**Result:** $MSG$ message is transmitted from $S$ to $D$

1 **Function** Routelee($S, D, MSG, n$): 
2 &nbsp;&nbsp;&nbsp;&nbsp;**if** $S == D$ or $n == 0$ **then** 
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0
4 &nbsp;&nbsp;&nbsp;&nbsp;**end**
5 &nbsp;&nbsp;&nbsp;&nbsp;**if** $S[n] \oplus D[n] == 1$ **then** 
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S[n] = D[n]$
7 &nbsp;&nbsp;&nbsp;&nbsp;**end**
8 &nbsp;&nbsp;&nbsp;&nbsp;return RouteMsg($S, D, MSG, n - 1$)
9 **End Function**

**Remark 4.3.** The algorithm 3 finds unicast routing for $CSNG(k, m)$ using divide and conquer process. First call of the route function is RouteMsg(10101, 10111, MSG, L). Recurrence relation
of the algorithm 3 is $T(L) = T(L-1) + \Theta(1)$ ans thus, the complexity is $\Theta(L)$ where L equal to $(k+m+2)$.

**Algorithm 4:** This algorithm calculate unicast routing for $CSNG(k, m)$ using divide and conquer approach (recursive process).

**Data:** $S$ = source, $D$ = destination, $direction: dir = S \oplus D$, $route: r = r[L]$ ($L$ elements in an array), $MSG$: message

**Result:** $MSG$ message is transmitted from $S$ to $D$ using $r$ where is an empty array with $L$ size

1 **Function** Route($S$, $dir$, $r$, $left$, $right$):

2 | **if** $left == right$ **then**
3 | | $r[left] = S \oplus \text{dir}[1, right]*2^{n-right}$
4 | | **return** 0
5 | **end**
6 | $mid = \lfloor(\text{left} + \text{right})/2\rfloor$
7 | Route($S$, $dir$, $r$, $left$, $mid$)
8 | Route($S$, $dir$, $r$, $mid + 1$, $right$)

9 **End Function**

10 **for** $i = 0$ to $L-1$ **do**

11 | $r[i+1] \stackrel{MSG}{\leftrightarrow} r[i]$

12 **end**

**Remark 4.4.** The Algorithm 4 finds unicast routing for $CSNG(k, m)$ using divide and conquer process. First call of the route function is Route(10101, 10111, $r$, $1$, $L$) (See fig. 5). Recurrence relation of the Algorithm 4 is $T(L) = 2T(L/2) + \Theta(1)$ and thus, the complexity is $\Theta(L)$ where $L$ equal to $(k+m+2)$.

The graph drawn in figure 6 is a non-simple graph because it contains a cycle(s). Algorithm 4 runs for the length of the $S$ or $D$ array. The number of nodes to be used for the routing operation will be as much as the length of the $S$ or $D$ array even there are fewer nodes on the shortest path. Therefore, some successive $r$ values in Algorithm 4 may be the same and transmit the same message back to itself.

4.1.1. *Parallel process.* By means of parallel programming, larger problems can be solved in a shorter time and performance can be increased. Parallel programming method helps to provide the required acceleration and efficiency by dividing different parts of the problems into different
<figure><img src="image_7.png" /><figcaption>FIGURE 5. Steps 1 to 9 in Algorithm 4</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>FIGURE 6. Graph representation of steps 10 to 12 in Algorithm 4</figcaption></figure>

processors in the solution of complex and large problems that have emerged with scientific developments. In parallel programming, the solution of a problem is carried out with the following steps;

* The problem is divided into parts,

* These parts are divided into equal time intervals.

* Each problem piece is processed synchronously on different processors at the same time and programming is carried out.

The most basic preference reasons for parallel programming are to prevent slowdowns in the computer by making the most appropriate use of memory by using multiple processors instead of
a single processor. In this way, computers can perform calculations quickly and this provides an increase in performance on the computer.

Unicast routing for hypercube is parallelized in for fault tolerant algorithms in different works ([24–27]). Unicast routing for $CSNG(k, m)$ can be performed in parallel to increase efficiency and decrease the running time. Using divide and conquer method, each iterations can be done in different processors. Dividing part is similar with merge sort. When the function calls itself, problem divides in half and when there the problem size is one, it calculates the $ith$ node address in the path.

There are three different cases for running time of the Algorithm 4 in parallel architecture depends on the address length of nodes and the number of processors and obtained by height of the recursive tree. Here, address length for $CSNG(k, m)$ is $k + m + 2$.

**Case 1.** The address length is smaller than or equal to $2^{n-1}$ while the number of processors is $2^n$ and $n$ is a natural number. For the Case 1, running time of the parallel algorithm is equal to $lg(address\ length)$.

When calculating the path between 2 nodes, the number of nodes on the longest route is equal to the address length of a node. So, the number of calculations on the road is equal to the address length. For each calculation of address on the path, one processor is used. Running time is calculated by ceiling the recursive division of the address length by 2. Therefore, if the address length is less than or equal to the half of the number of processors, the running time is calculated using address length. Since address length $2^{n-1}$ and number of processors = $2^n$ and $n \in N$

$$T(n) = lg(address\ length) = lg(k + m + 2)$$

**Case 2.** If the address length is greater than the half of the number of processors and less than or equal to the number of processors while number of processors is $2^n$ and $n$ is a natural number, running time is calculated using the number of processors. For the case 2, running time of the parallel algorithm is equal to $lg(number\ of\ processors)$, which is the height of the recursion tree. Since the number of the processors is 2 to the nth power, tree height is $n$, so the running time is also $n$. Since $2^{n-1} < address\ length \le 2^n$ and $n \in N$,

$$T(n) = lg(number\ of\ processors) = lg(2^n)=n.$$

**Case 3.** The address length is bigger than the number of processors while number of processors is $2^n$ and $n$ is a natural number. In case 3, running time is calculated using both the address length and the number of processors. The running time of the parallel algorithm is equal to $lg(number\ of\ processors)$ is multiplied by 2 to the power the difference between $lg(address\ length)$ and $lg(number\ of\ processors)$, which is the difference between height of the recursion trees for the address length and the number of processors. Since address length > $2^n$ and $n \in N$,
$$ 
\begin{aligned}
T(n) &= 2^{\lceil \lg(\text{address length}) \rceil} - \lg(\text{number of processors}) \lg(\text{number of processors}) \\
&= 2^{\lceil \lg(k+m+2) \rceil} - \lg(2^n) \lg(2^n) \\
&= n2^{\lceil \lg(k+m+2) \rceil} - n
\end{aligned}
$$

Since the algorithm calculates the change of each bit on the address separately, it also calculates the address for the unchanging bits while finding path. Therefore, the graph of the message sending process may not be obtained as a simple graph because of loops, as seen in Figure 6.

## 4.2. Broadcasting algorithms.
In this subsection, the focus will be on broadcasting algorithms with the help of hypercube's broadcasting algorithms.

**Remark 4.5.** Broadcasting algorithms (Algorithm 5 and Algorithm 6) for $CSNG(k, m)$ can be obtained similarly by writing $k+m+2$ instead of $2k+2$ in Algorithm 2 and Algorithm 3 in [6]. The costs for these 2 algorithms can be obtained by writing $k+m+2$ instead of $2k+2$ the complexity in Algorithm 2 and Algorithm 3 in [6]. Actually, since this mesh structure ($CSNG(k, m)$) is constructed as a hypercube variant, the broadcasting algorithms for this mesh structure exhibit different behavior than standard mesh algorithms (see Fig 7-12 in appendix).

# 5. CONCLUSIONS

In this paper, we developed new algorithms for Connected square network graphs ($CSNG(k, m)$). Since this graph is a hypercube graph, the algorithms obtained for this graph are more similar to hypercube algorithms than classical mesh algorithms. First algorithm is for finding alternative Hamiltonian path for $CSNG$ with using dynamic programming with running time as $O(k+m)$. Second algorithm calculating the unicast routing for $CSNG(k, m)$ and running time of it is $O(k+m+2)$, same as parallel unicast routing algorithm, which is a divide and conquer algorithm. The use of parallel and distributed architecture provides performance improvements at runtime according to the number of processors. The most general of the runtime calculations for the three case of parallel unicast algorithm is $T(n) = 2^{\lceil \lg(\text{address length}) \rceil} - \lg(\text{number of processors}) \lg(\text{number of processors})$ where address length of $CSNG(k, m)$ is $k+m+2$. Broadcasting algorithms for $CSNG$ can be easily obtained with similar strategy as the broadcasting algorithms of hypercube.

# REFERENCES

[1] J.P. Hayes, T.N. Mudge, Q.F. Stout, Architecture of a hypercube supercomputer, in: Proc. ICPP, 1986, pp. 653–660.

[2] J. Nieminen, M. Peltola, P. Ruotsalainen, J. Nieminen. “On graphs like hypercubes.” Tsukuba Journal of Mathematics 32, no. 1 (2008): 37–48.

[3] G.B. Chae, E.M. Palmer, R.W. Robinson, Counting labeled general cubic graphs, Discrete Mathematics 307 (2007) 2979 – 2992.

[4] F. Harary, J.P. Hayes and H-J Wu, A survey of the theory of hypercube graphs. Comput. Math. Applic., 1988, Vol. 15, No. 4, 277-289.
**Algorithm 5:** This algorithm calculate one to all broadcasting for $CSNG(k, m)$ using divide and conquer approach.

**Data:** $my_label = 0, t = k + m + 1, mask = (2^{k+m+2} - 1) \oplus 2^{m+k+1}$

**Result:** MSG message is transmitted from one node to all nodes

1. **Function One_to_all_broadcasting(k, m, my_label, MSG, mask, t):**

2. **if** $t >= 0$ **then**
3. &nbsp;&nbsp;&nbsp;&nbsp;**if** $my_label \cap mask == 0$ **then**
4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $my_label \cap 2^t == 0$ **then**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`destination_label = my_label \oplus 2^t`
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;send MSG to `destination_label`
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
8. &nbsp;&nbsp;&nbsp;&nbsp;**else**
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`source_label = my_label \oplus 2^t`
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;send MSG to `source_label`
11. &nbsp;&nbsp;&nbsp;&nbsp;**end**
12. **end**
13. `One_to_all_broadcasting(k, m, my_label, MSG, mask \cap 2^t, t - 1)`

14. **end**
15. **End Function**

[5] W. Mao, D.M. Nicol, On k-ary n-cubes: theory and applications, Discrete Applied Mathematics 129 (2003) 171-193.

[6] A. Karci, B. Selcuk, A new hypercube variant : Fractal Cubic Network Graph. Engineering Science and Technology, An International Journal 18(1): (2014) 32-41.

[7] B. Selcuk, A. Karci, Connected Cubic Network Graph. Engineering Science and Technology, an International Journal 20(3): (2017) 934-943.

[8] A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Trans. Parallel Distrib. Syst. 2 (1) (1991) 31-42.

[9] H.Y. Chang, R.J. Chen, Incrementally extensible folded hypercube graphs, J. Inf. Sci. Eng 16 (2) (2000) 291-300.

[10] Q. Dong, X. Yang, J. Zhao, Y.Y. Tang, Embedding a family of disjoint 3D meshes into a crossed cube, Inf. Sci. 178 (2008) 2396-2405.

[11] K. Efe, The crossed cube architecture for parallel computation, IEEE Trans. Parallel Distrib. Syst. 40 (1991) 1312-1316.

[12] C.J. Lai, C.H. Tsai, H.C. Hsu, T.K Li, A dynamic programming algorithm for simulation of a multi-dimensional torus in a crossed cube, Inf. Sci. 180, (2010) 5090-5100.
**Algorithm 6:** This algorithm calculate all to all broadcasting for $CSNG(k, m)$ using divide and conquer approach.

**Data:** $my_label = 0, t = 0$

**Result:** $MSG$ message is transmitted using all nodes

1. **Function** All_to_all_broadcasting($k, m, my_label, my_MSG, t$):

<table><tr><td>2</td><td><pre>if t &lt; k + m + 2 then</pre></td></tr><tr><td>3</td><td><pre>partner_label = my_label &oplus; 2<sup>t</sup></pre></td></tr><tr><td>4</td><td><pre>send my_MSG to partner_label</pre></td></tr><tr><td>5</td><td><pre>receive MSG from partner_label</pre></td></tr><tr><td>6</td><td><pre>my_MSG = my_MSG &cup; MSG</pre></td></tr><tr><td>7</td><td><pre>All_to_all_broadcasting(k, m, my_label, my_MSG, t + 1)</pre></td></tr><tr><td>8</td><td><pre>end</pre></td></tr></table>

9. **End Function**

[13] M. Abd-El-Barr, T.F. Soman, Topological properties of hierarchical interconnection networks a review and comparison, J. Electr. Comput. Eng. (2011) (01/2011).

[14] K. Ghose, K.R. Desai, Hierarchical cubic networks, IEEE Trans. Parallel Distrib. Syst. 6 (1995) 427-435.

[15] A. Karci, Hierarchical extended fibonacci cubes, Iran. J. Sci. Technol. Trans. B Eng. 29 (2005) 117-125.

[16] A. Karci Hierarchic graphs based on the fibonacci numbers, Istanbul Univ. J. Electr. Electron. Eng. 7 (1) (2007) 345-365.

[17] B. Selçuk, Connected Square Network Graphs. Universal Journal of Mathematics and Applications, 5 (2), 57-63, (2022) DOI: 10.32323/ujma.1058116

[18] B. Selçuk, A.N.A. Tankül, "A New Hypercube-like Graph", Turkish Journal of Mathematics-Studies on Scientific Developments in Geometry, Algebra, and Applied Mathematics, (pp. 85), Ankara, Türkiye, (February 2022)

[19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition, vol. 7. The MIT Press, 2001.

[20] G. Reinelt. The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag, 1994.

[21] R. J. Wilson, Introduction to Graph Theory, 4th ed. Harlow: Addison Wesley Longman Limited, 1996.

[22] V. Kumar, A. Grama, A. Gupta, G. Karypis Introduction to Parallel Computing: Design and Analysis of Algorithms The Benjamin/Cummings Publishing Company (1994)

[23] A. Y. Al-Dubai and M. Ould-Khaoua, "On the design of scalable pipelined broadcasting for mesh networks," Proc. - Int. Symp. High Perform. Comput. Syst. Appl., vol. 2002-January, pp. 98-105, 2002, doi: 10.1109/HPCSA.2002.1019140.

[24] S. Gunes, N. Yilmaz, and E. Yaldiz, "Fault tolerant unicast routing algorithm based on parallel branching method for faulty hypercube," in ICECS 2001. 8th IEEE International Conference on Electronics, Circuits and Systems (Cat. No.01EX483), 2001, vol. 1, pp. 103-106 vol.1, doi: 10.1109/ICECS.2001.957686.

[25] Q.-P. Gu and S. Peng, "Optimal Algorithms for Node-to-Node Fault Tolerant Routing in Hypercubes," Comput. J., vol. 39, no. 7, pp. 626-629, 1996, doi: 10.1093/comjnl/39.7.626.
[26] M.-S. Chen and K. G. Shin, "Depth-first search approach for fault-tolerant routing in hypercube multicomputers," IEEE Trans. Parallel & Distrib. Syst., vol. 1, no. 02, pp. 152-159, 1990.

[27] H. M. A. Fahmy and A. A. ElHefnawy, "Methods for distributed unicast in hypercubes," J. Syst. Archit., vol. 48, no. 6, pp. 193-198, 2003, doi: https://doi.org/10.1016/S1383-7621(02)00136-4.

## 6. APPENDIX

<figure><img src="image_9.png" /><figcaption>FIGURE 7. All steps for one to all broadcasting for $CSNG(k, m)$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 8. Base case for all to all broadcasting for $CSNG(k, m)$</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>FIGURE 9. First step for all to all broadcasting for $CSNG(k, m)$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>FIGURE 10. Second step for all to all broadcasting for $CSNG(k, m)$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>FIGURE 11. Third step for all to all broadcasting for $CSNG(k, m)$</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>FIGURE 12. Fourth step for all to all broadcasting for CSNG(k, m)</figcaption></figure>