Application of the Hamiltonian circuit Latin square to a Parallel Routing Algorithm on Generalized Recursive Circulant Networks

Journal of Korea Multimedia Society.
2015.
Sep,
18(9):
1083-1090

- Received : April 30, 2015
- Accepted : July 28, 2015
- Published : September 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

A generalized recursive circulant network(GR) is widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on this network, that is a key to the performance of this network. We would like to transmit maximum number of packets from a source node to a destination node simultaneously along paths on this network, where the
i^{th}
packet traverses along the
i^{th}
path. In order for all packets to arrive at the destination node securely, the
i^{th}
path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian Circuit Latin Square(HCLS), a special class of (n x n) matrices, we present O(n
^{2}
) parallel routing algorithm on generalized recursive circulant networks.
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
) has
vertices where
m_{i}
≥ 2 for 1 ≤
i
≤
h
. Index I is a dimension of the labeling system while
m_{i}
is the base of dimension
i
. Each vertex in the network can be expressed as an
h
-tuple (
x_{h}
,
x
_{h-1}
,...,
x
_{1}
) with 0 ≤
x_{i}
≤
m_{i}
- 1 for
i
= 1,2,...,
h
. The number of edges at a node is
, if
m_{i}
> 2, then
k_{i}
= 2, else
k_{i}
= 1.
The routing of message is thus a key to performance of networks. We look for algorithms that are capable of handling, multiple data items simultaneously transmitted from a starting node to a destination node. There are a few algorithms on the hypercube-like network that allow us to locate n disjoint paths such as the Hamiltonian path Algorithm
[2]
, the Rotation Algorithm using Tree Structure
[3]
, the Disjoint Path Algorithm
[3]
, and the Routing Algorithms
[4]
. Node-disjoint paths can be categorized into three classes-one-to-one, one-to- many, and many-to-many. The first class considers the disjoint paths from a source node to a destination node, the second from a source node to k destination nodes and the third from k source nodes to k destination nodes. One-to-one disjoint paths were constructed on several networks such as hypercubes
[5]
, k-ary n-cubes
[6]
and star graphs
[7]
. One-to-many disjoint paths were designed on hypercubes
[8
,
9]
and star graphs
[8]
. For the generation of many-to-many disjoint paths some work has been done
[10
,
11]
.
In this paper, we propose an algebraic approach to routing of messages on
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
). As described above, maximum number of packets are simultaneously transmitted from a starting node to a destination node, where the
i^{th}
packet is sent along the
i^{th}
path. In order for all packets to arrive at a destination node quickly and securely, the
i^{th}
path must be node-disjoint from all other paths. To accomplish this, we employ the operations of nodes presented in Cayley Graph
[12]
and the special matrix called as Hamiltonian Circuit Latin Square(HCLS)
[5]
, which was used to find a set of node-disjoint paths on hypercube network
[5]
, circulant networks
[13]
and recursive cube of rings networks
[14]
.
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
). The paper’s objective is to find algorithms that will facilitate the transmission of data from a source node to a desired node on generalized recursive circulant networks. In order for the data to traverse to a desired node, it must cross, successively, intermediate nodes along a path.
Definition 1.
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
) is defined as follows:
Each vertex in the network can be expressed as an
h
-tuple (
x_{h}
,
x
_{h-1}
,...,
x
_{1}
) with 0 ≤
x_{i}
≤
m_{i}
- 1 for
i
= 1,2,...,
h
and the edge set E is {(
v
,
w
)|
w
= (
x_{h}
,...,
x_{i}
,...,
x
_{1}
), +
i
^{±}
= (
x_{h}
,...,
x_{i}
± 1,...,
x
_{1}
), where
v
= (
x_{h}
,...,
x_{i}
,...,
x
_{1}
), if
x_{i}
+ 1 =
m
, then
x_{i}
= 0,
x
_{i+1}
=
x_{i}
+ 1 and if
x_{i}
- 1 = -1, then
x_{i}
=
m_{i}
- 1,
x
_{i+1}
=
x
_{i+1}
- 1.
The number of edges at a node is
, if
m_{i}
> 2, then
k_{i}
= 2, else
k_{i}
= 1. It means that if
m_{i}
> 2, then (
m_{h}
,...,
m_{i}
,...,
m
_{1}
) has two edges at dimension
i
- (
m_{h}
,...,
m
_{i+1}
,...,
m
_{1}
) and (
m_{h}
,...,
m_{i}
- 1,...,
m
_{1}
), else it has one edge - (
m_{h}
,...,
m
_{i+1}
,...,
m
_{1}
). When the operations occur at the leftmost dimension
m_{h}
, since
m
_{h+1}
is invisible, addition and subtraction to
m
_{h+1}
are neglected. This means that vertices (0,
x
_{h-1}
,...,
x
_{1}
) and
m_{h}
- 1,
x
_{h-1}
,...,
x
_{1}
) are adjacent (see
Fig. 1
).
GR (2,4,3).
Researches on generalized recursive circulant networks(GR) are actively performed in graphic-theoretical areas such as embedding and faulttolerance. As mentioned earlier, a node on Cayley Graph can traverse to another node by performing a certain operation. We now employ these operations to GR.
Definition 2. The Routing function R for
i
^{±}
is as follows:
R
_{i±}
(
A
) =
A
+
i
^{±}
(mod
n
), where A is an address of a node
Node A is physically connected to k neighboring nodes and these paths are node-disjoint. Data is transmitted from a source node along the
i^{th}
path. The path above is selected by the routing function described in Definition 2. To do this, the relative address of two nodes can be obtained below.
Definition 3. Let A and B be (
a_{h}
,
a
_{h-1}
,...,
a_{i}
,...,
a
_{1}
) and (
b_{h}
,
b
_{h-1}
,...,
a_{i}
,...,
b
_{1}
), respectively. The relative address
r
of nodes A and B is computed as the difference between each dimension of two nodes.
Let A and B be (1,2,1) and (3,2,2) on GR(4, 5, 3). The relative address
r
is (2,0,1), which can be described as a sequence
S
of operations <3
^{+}
,3
^{+}
,1
^{+}
> since
r
_{3}
= 2 and
r
_{1}
= 1. Also,
x
^{+}
is interchangeable to
x
and
S
is <3,3,1>.
Definition 4. Let
T(A,S)
be a logical transmission path starting form node A to a destination node, where r is a multiset and a sequence of operations, via which data can reach at a destination node.
T(A,S)
is determined by the order of elements in
S
.
Given node
A
and multiset
S
on
GR(4,5,3)
, we would like to transmit to a destination node via intermediate nodes. Let node
A
and set
S
be (1,2,1) and <3,3,1>, respectively. Operations in S are applied to the routing function sequentially and then the traversal of data is (1, 2, 1) → (2, 2, 1) → (3, 2, 1) → (3, 2, 2).
Since the paper’s objective is to find an algorithm that will facilitate the secure transmission of data from a starting node to a destination node, those operations should be appropriate for this objective. Given S, a size of this sequence must be minimized since a routing distance is equal to a size of a sequence.
For example, supposed that
S
= < 1
^{-}
,1,1,1,3,3,1
^{-}
> on
GR(4,5,3)
. then
S
can be minimized to < 1
^{-}
,2,3,3,1
^{-}
>since
x
_{1}
+ 1 + 1 + 1 (mod 3) =
x
_{1}
and a carry 1 is added to
x
_{2}
.
The operations applied at the first step and the last step.
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
). In this section, we would like to construct a set of k node-disjoint paths in order to transmit these packets safely. First, k packets residing at a node are sent to its neighboring nodes along a set of disjoint paths. These paths are generated by employing k different operations at the beginning step and by performing k different operations at the last step in order to arrive at a destination node. The figure below illustrates the operations applied to generate k paths from a source node to a destination node.
The
i^{th}
packet is transmitted along the
i^{th}
path, the first intermediate node of which is obtained from applying operation
s_{i}
at a starting node and the last intermediate node transmits this packet to a destination node by applying operation
p_{i}
. In some cases,
s_{i}
and
p_{i}
can be the same.
Definition 5. Let
O^{s}
be a set of operations occurring at a starting node when k packets are transmitted simultaneously and Let
O^{d}
be a set of operations occurring at the last k intermediate nodes in order for k packets to arrive at a destination node. These sets are defined as follows:
We now apply the HCLS(Hamiltonian Circuit Latin Square) to find a set of m shortest and node-disjoint paths. A latin square is a square ma-trix with
m
^{2}
entries of m different elements, none of the elements occurring twice within any row or column of the matrix. The integer m is called the order of latin square. The next definition describes the HCLS.
Definition 6. The HCLS
M
^{1}
is constructed as follows: Given distinct m points
a
_{0}
,
a
_{1}
,...,
a
_{m-2}
,
a
_{m-1}
,
a
, a Hamiltonian circuit ,
a_{i}
,→
a_{j}
→…→
a_{k}
→,
a_{i}
, is randomly selected. On the circuit each row of
M
^{1}
can be obtained from the Hamiltonian path. starting at any position
a_{k}
(0 ≤
k
≤
m
- 1), under the condition that no two rows begin at the same position. If a Hamiltonian path is ,
a_{i}
,→
a_{j}
→…→
a_{k}
, then the row obtained from it is [,
a_{i}
,
a_{j}
,...
a_{k}
].
From the HCLS given in Definition 6, the MHCM(Modified Hamiltonian Circuit Matrix) is constructed below.
Definition 7. Given the HCLS
M
^{1}
= (
a_{ij}
), the MHCM
M
^{2}
is constructed as follows:
M
^{2}
= (
A_{ij}
),
A_{ij}
= (
a
_{i,0}
,
a
_{i,1}
,...,
a
_{i,j-1}
,
a_{i,j}
),
a_{ij}
∈
Z_{m}
,0 ≤
i
≤
m
- 1,0 ≤
j
≤
m
- 2.
The following example will provide a better understanding of Definition 6 & 7.
Example 1. If the Hamiltonian path is 2 → 3 → 1 → 4, then the HCLS
M
^{1}
and the MHCM
M
^{2}
are constructed as follows.
Definition 8. Call
M
^{3}
the MGNDP(Matrix for Generating Node-Disjoint Paths). No two entries of this matrix are the same. It satisfies the following conditions.
0 ≤
i
≤
m
- 1,0 ≤
j
≤
m
- 2
s
means “stay at the current node”.
Referring to
[5]
, the MHCM satisfies the conditions of the MGNDP(Matrix for Generating Node-Disjoint Paths), which constructs a set of node-disjoint paths on the hypercube network. Since The HCLS belongs to the latin square, a set of elements in the first column is the same as that of the last column. On generalized recursive circulant networks, an element in the HCLS is represented as an operation. Also,
O^{s}
and
O^{d}
in Definition 5 are described as all the elements in the first column and all the elements in the last column, respectively. We, intuitively, realize that a set of m node-disjoint paths is generated if the number of distinct sequences of operations for arriving at an arbitrary node in a short time is
m
(
m
≤
k
). The remaining operations excluding these distinct operations from
O^{s}
and
O^{d}
, should be performed.
Example 2. Let A and B be (1,2,1) and (3,2,2) on
GR
(4,5,3). According to Definition 4, sequence S is computed as < 3, 3, 1 > and a set of node-disjoint paths is generated as follows. A set of distinct operations in S is < 1, 3 >. Using these operations, (2 × 2) HCLS can be obtained from Definition 6.
Operations in the
i^{th}
row of the HCLS generated above are performed for traversal of the
i^{th}
packet and the remaining operation is also executed at the point except the first and the last points. In order to assure that these paths are node-disjoint, the remaining operation should be executed at the same time. In this example, the running point of the remaining operation is the second. Physical transmission paths from node A to node B are described below.
From Definitions 1 and 6,
O^{s}
and
O^{d}
are obtained, that is,
O^{s}
=
O^{d}
= {1,1
^{-}
,2,2
^{-}
,3,3
^{-}
}. Excluding the operations 1 and 3, which are performed in the first and the last steps, from
O^{s}
and
O^{d}
,
O^{s}
and
O^{d}
become {1
^{-}
,2,2
^{-}
,3}. Recall that we deal with design of six node-disjoint paths, out of which two node-disjoint paths are now constructed. Examining Definition 2, when a packet traverses in a positive direction on the
i^{th}
dimension and then traverses in a reverse direction on the same dimension, a packet comes back to its original position. This idea is applied to generation of disjoint paths. If {
i
,
i
^{-}
} exists as a subset of
O^{s}
and
O^{d}
, these operations are executed at the first and the last steps and the operations obtained from design of the shortest distance at the middle steps. Path 3 and Path 4 are constructed below.
Excluding { 2,2
^{-}
} from
O^{s}
and
O^{d}
,
O^{s}
and
O^{d}
become { 1
^{-}
,3
^{-}
}. While operations working at the first and the last steps are not the same, operations performing at the remaining steps are the same. As described earlier for Path 3 and Path 4, a packet traverses in a positive direction on the
i^{th}
dimension and then traverses in a reverse direction on the same dimension. Likewise a packet traverses twice in the same direction on the
i^{th}
dimension and then traverses twice in the reverse direction on the same dimension, and then this packet comes back to its original position. A sequence of operations for a path is now obtained. Firstly, two operations traversed in the same direction are chosen for the first and the last steps. Secondly, two operations in reverse direction and the operations for the shortest distance would be executed at the middle steps. However, these operations must be minimized in order to be a shortest path and then the minimal operations are executed. Paths 5 and 6 are generated by handling cases of {1
^{-}
} and {3
^{-}
}, respectively.
The process to find a set of node-disjoint paths is described above. We now propose a parallel routing algorithm that generates a set of node-disjoint paths on generalized recursive circulant networks. In this paper, we will use the term “distance” between two nodes to refer to the number of routing steps(also called hopcounts) needed to send a message from one node to another.
begin
(1) Compute the relative address r of nodes A and B
(2) Using the relative address r, a sequence S of operations to arrive at node B in a short time are produced.
(3) In order to design a set of node-disjoint paths, find a sequence
S
_{1}
of distinct elements in S. A set of |
S
_{1}
| shortest and node-disjoint paths are generated. Each path of length is | S |,
(3-1) Using
S
_{1}
, (n × n) HCLS is constructed, where n = |
S
_{1}
|.
(3-2) Operations in the
i^{th}
row of the HCLS are performed for traversal of the
i^{th}
packet and the remaining operations in S should be executed at the point except the first and the last points.
(3-3)
O^{s}
←
O^{s}
−
S
_{1}
and
O^{d}
←
O^{d}
−
S
_{1}
(4) Construct two node-disjoint paths, each path has length |
S
| + 2.
(4-1) If
O^{s}
=
ϕ
, the process is finished.
(4-2) If a set of {
i
,
i
^{-}
} is found in
O^{s}
, then these operations are performed at the first and the last steps, and the operations in S at the middle steps, otherwise go to (5).
(4-3)
O^{s}
←
O^{s}
- {
i
,
i
^{-}
},
O^{d}
←
O^{d}
- {
i
,
i
^{-}
} and go to (4-1).
(5) Generate the remaining paths.
(5-1) If
O^{s}
=
ϕ
, the process is finished.
(5-2) For
i
∈
O^{s}
(
m_{i}
> 2), produce
S
_{2}
of mini-mum number of operations by reducing the size of S ∪ {
i
^{-}
,
i
^{-}
},
S
_{2}
= {i, min(S ∪ {
i
^{-}
,
i
^{-}
}), i}
(5-3) Operation i is performed at the first and the last steps and the remaining operations of
S
_{2}
are executed at the middle steps.
(5-4)
O^{s}
←
O^{s}
- {
i
},
O^{d}
←
O^{d}
- {
i
} and go to (5-1).
end.
GR_Routing_Algorithm
is thus fairly straightforward. The time involved in performing Steps (1), (2) and (4) is small compared to the remaining steps. The first, second and fourth steps of this algorithm does not, therefore, contribute to an objectionable overhead.
Theorem 1. The construction of a set of k node-disjoint paths can be performed in
O(n^{2})
time.
Proof: Applying the Algorithm above to generate k node-disjoint paths. Important steps for determining time complexity requisite for the Algorithm are two things. One is to design the HCLS, which requires
O(n)
. The other is to run Step (5) of
GR_Routing_Algorithm
. In Step (5), in order to run
i
in
O^{s}
at the first and the last steps in transmission, a sequence of operations is de-termined to S ∪{
i
^{-}
,
i
^{-}
}, and is reduced. Since the reduction process requires O(n) time and the number of elements in
O^{s}
is less than n, Step (5) can be computed in
O(n^{2})
. Therefore, a set of k node-disjoint paths can be created in
O(n^{2})
time.
The paper’s objective is to find a set of k node-disjoint paths between two nodes. The major topological characteristics of the generalized recursive circulant network is considered and the property of k paths obtained from the Algorithm is proven below.
Theorem 2. The k transmission paths produced by
GR_Routing_Algorithm
are node-disjoint.
Proof: The k packets residing at node A are now transmitted at time
t
_{0}
. These packets reach to its k neighboring nodes at time
t
_{1}
. Then, each packet traverses to a neighboring node along a shortest path. Suppose that two packets arrive at the same node except a destination node during transmission. In order for this case to occur, the following condition should be satisfied. Let
S_{i}
and
S_{j}
be two sequences of operations for sending two packets from a starting node to two arbitrary nodes at time
t_{ij}
, where
t_{ij}
means that one packet arrives at time
t_{i}
and the other arrives at time
t_{j}
. Then,
S_{i}
and
S_{j}
should be the same. In other words, if these sequences do not appear, a set of node-disjoint paths can be constructed. According to the Algorithm described above, three classes of paths are generated on this network. We now consider three cases.
Case 1: Let
S
_{1i}
and
S
_{1j}
be two sequences of operations obtained from design of the shortest distance. Then
S
_{1i}
and
S
_{1j}
must not be the same due to the properties of the MGNDP.
Case 2: Let
S
_{2i}
and
S
_{2j}
be two sequences of operations acquired by running Algorithm-(4). Then
S
_{2i}
and
S
_{2j}
must not be the same because the first elements of
S
_{2i}
and
S
_{2j}
are
S_{k}
and
, respectively and the rests of them are the same. In order for paths generated through case 1 and case 2 to be node-disjoint, we prove that
S
_{1i}
and
S
_{2j}
must not be the same. Considering the first element
S_{k}
of
S
_{2j}
, it is not an element of
S
_{1j}
. Therefore, these sequences are different all the times.
Case 3: Let
S
_{3i}
and
S
_{3j}
be two sequences of operations generated by performing Algorithm-(5), and T be a sequence of operations, which creates a shortest path from a source node to a desired node. Then, the first elements of
S
_{3i}
and
S
_{3j}
do not belong to T,
S
_{3i}
does not contain the first element of
S
_{3j}
, and
S
_{3j}
does not contain the first element of
S
_{3i}
. So,
S
_{3i}
and
S
_{3j}
should not be the same.
To prove that the paths created by all the cases are node-disjoint,
S
_{3i}
and
S
_{2j}
must not be the same. The method of proof is the same as the case 2. Looking into the first element of
S
_{2j}
, the element is not a part of
S
_{3i}
. Therefore, these sequences are different all the time.
GR
(
m_{h}
,
m
_{h-1}
,...,
m
_{1}
) employing the Hamiltonian Circuit Latin Square(HCLS). Important steps for determining time complexity requisite for the algorithm are two things. One is to design the HCLS, which needs
O(n)
. The other is to execute Step (5) of
GR_Routing_Algorithm
, which requires
O(n^{2})
. Therefore, we can create
O(n^{2})
parallel routing algorithm for constructing a set of k node-disjoint paths.
Dongmin Choi
He received his B.E. degree from the Kyunghee University in 2003 and M.S. and Ph.D. degrees in computer Science from Chosun University in 2007 and 2011, respectively. He is working as a researcher in Computer Science at Chosun University. His research interests are in information security, sensor network systems, mobile ad-hoc systems, smart grid home network systems and internet ethics.
Ilyong Chung
He received the B.E. degree from Hanyang University, Seoul, Korea, in 1983 and the M.S. and Ph.D. degrees in Computer Science from City University of New York, in 1987 and 1991, respectively. From 1991 to 1994, he was a senior technical staff of Electronic and Telecommunication Research Institute (ETRI), Dajeon, Korea. Since 1994, he has been a Professor in Department of Computer Science, Gwangju, Korea. His research interests are in computer networking, security systems and coding theory.

1. INTRODUCTION

A generalized recursive circulant network(GR)
[1]
is widely used in the design and implementation of local area networks and parallel processing architectures.
This network denoted by
PPT Slide

Lager Image

PPT Slide

Lager Image

2. DESIGN OF THE SHORTEST PATH

Let A and B be any two nodes on
PPT Slide

Lager Image

PPT Slide

Lager Image

- r= (bh-ah,bh-1-ah-1,...,bi- ,ai,...,b1-a1)

PPT Slide

Lager Image

3. Application of the Hamiltonian Circuit Latin Square to the Parallel Routing Algorithm on Generalized Recursive Circulant Networks

The k packets are transmitted from a source node to a destination node on
- Os= {s1,s2,...,sk-1,sk}
- Od= {p1,p2,...,pk-1,pk}
- Os=Od

PPT Slide

Lager Image

- M3= (Ai,j),Ai,j⊂ {Zm∪ {s}},

- (1) |Ai,j| =j+ 1
- (2)Ai,j≠Ak,l,ifi≠k
- (3)Ai,j⊂Ai,j+1
- (4)Ai,j+1=Ai,j∪{s}, ifs∈Ai,j

PPT Slide

Lager Image

- Path 1 : T(A,< 1, 3, 3 >) : A → (1, 2, 2) → (2, 2, 2) → B
- Path 2 : T(A,< 3, 3, 1 >) : A → (2, 2, 1) → (3, 2, 1) → B

- Path 3 :T(A< 2,1,3,3,2->) : A → (1, 3, 1) → (1, 3, 2) → (2, 3, 2) → (3, 3, 2) → B
- Path 4 :T(A< 2-,1,3,3,2->) : A → (1, 1, 1) → (1, 1, 2) → (2, 1, 2) → (3, 1, 2) → B

- Path 5 :
- T(A,< 1-,1,1,1,3,3,1->) =T(A,< 1-,2,3,3,1->): A → (1, 2, 0) → (1, 3, 0) → (2, 3, 0) → (3, 3, 0) → B
- Path 6 :
- T(A,< 3-,3,3,3,3,1,3->) =T(A,< 3-,1,3,- >): : A → (0, 2, 1) → (0, 2, 2) → B

- GR_Routing_Algorithm
- A ← an address of a starting node A
- B ← an address of a destination node B
- Os← a set of operations occurring at a starting node A
- Od← a set of operations requisite for reaching to a destination node B

PPT Slide

Lager Image

4. CONCLUSION

In this paper, we present the algorithm that generates a set of k node-disjoint paths on
BIO

Tang S.
,
Wang Y.
,
Li C.
2012
“Generalized Recursive Circulant Graphs,”
IEEE Transactions on Parallel Distributed Systems
23
(1)
87 -
93
** DOI : 10.1109/TPDS.2011.109**

Chung I.
2013
“Design of a Set of One-to-Many Node-Disjoint and Nearly Shortest Paths on Recursive Circulant Networks,”
Journal of Korea Multimedia Society
16
(7)
897 -
904
** DOI : 10.9717/kmms.2013.16.7.897**

Johnson S.L.
,
Ho C.
1989
“Optimum Broadcasting and Personalized Communication in Hypercube,”
IEEE Transactions on Computer
38
(9)
1249 -
1268
** DOI : 10.1109/12.29465**

Rabin M.O.
1989
“Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance,”
Journal of Association for Computing Machinery
36
(2)
335 -
348
** DOI : 10.1145/62044.62050**

Chung I.
1992
“Application of the Special Latin Squares to the Parallel Routing Algorithm on Hypercube,”
Journal of Korea Information Science Society
19
(5)
569 -
578

Shih Y.
,
Kao S.
2011
“One-to-one Disjoint Path Covers on K-ary N-cubes,”
Theoretical Computer Science
412
(35)
4513 -
4530
** DOI : 10.1016/j.tcs.2011.04.035**

Day K.
,
Tripathi A.
1994
“Comparative Study of Topological Properties of Hypercubes and Star Graphs,”
IEEE Transactions on Parallel Distributed Systems
8
(1)
1196 -
1202

Gao S.
,
Novick B.
,
Qiu K.
1998
“From Hall Matching Theorem to Optimal Routing on Hypercubes,”
Journal of Combinatorial Theory, Series B
74
(2)
291 -
301
** DOI : 10.1006/jctb.1998.1850**

Lai C.
2012
“Two Conditions for Reducing the Maximal Length of Node-Disjoint Paths in Hypercubes,”
Theoretical Computer Science
418
82 -
91
** DOI : 10.1016/j.tcs.2011.11.009**

Gu Q.
,
Peng S.
2000
Theoretical Computer Science
Networks
35
(1)
83 -
90
** DOI : 10.1002/(SICI)1097-0037(200001)35:1<83::AID-NET7>3.0.CO;2-D**

Madhavapeddy S.
,
Sudborough I. H.
“A Topogical Property of Hypercubes: Node Disjoint Paths,”
Proceedings of the Second IEEE Symposium on Parallel Distributed Processing
1990
532 -
539

Zhou J.
,
Wu Z.
,
Yang S.
,
Yuan K.
2015
”Symmetric Property and Reliability of Balanced Hypercube,”
IEEE Transactions on Computers
64
(3)
876 -
881
** DOI : 10.1109/TC.2014.2304391**

Cho Y.
,
Chung I.
2006
“A Parallel Routing Algorithm on Circulant Networks Employing the Hamiltonian Circuit Latin Square,”
Information Sciences
176
(21)
3132 -
3142
** DOI : 10.1016/j.ins.2005.12.014**

Choi D.
,
Lee O.
,
Chung I.
2008
“A Parallel Routing Algorithm on Recursive Cube of Rings Networks Employing Hamiltonian Circuit Latin Square,”
Information Sciences
178
(6)
1533 -
1541
** DOI : 10.1016/j.ins.2007.10.028**

Citing 'Application of the Hamiltonian circuit Latin square to a Parallel Routing Algorithm on Generalized Recursive Circulant Networks
'

@article{ MTMDCW_2015_v18n9_1083}
,title={Application of the Hamiltonian circuit Latin square to a Parallel Routing Algorithm on Generalized Recursive Circulant Networks}
,volume={9}
, url={http://dx.doi.org/10.9717/kmms.2015.18.9.1083}, DOI={10.9717/kmms.2015.18.9.1083}
, number= {9}
, journal={Journal of Korea Multimedia Society}
, publisher={Korea Multimedia Society}
, author={Choi, Dongmin
and
Chung, Ilyong}
, year={2015}
, month={Sep}