Optimal Parallel Routing in Star Networks.
AbstractStar networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
Introduction
The star network [2] has received considerable attention recently by researchers as a graph model
for interconnection network. It has been shown that it is an attractive alternative to the widely used
hypercube model. Like the hypercube, the star network is vertex- and edge-symmetric, strongly
hierarchical, and maximally fault tolerant. Moreover, it has a smaller diameter and degree while
comparing with hypercube of comparable number of vertices.
The rich structural properties of the star networks have been studied by many researchers. The
n-star network S n is a degree 1)-connected, and vertex symmetric Cayley graph [1, 2].
Jwo, Lakshmivarahan, and Dhall [15] showed that the star networks are hamiltonian. Qiu, Akl,
and Meijer [22] showed that the n-star network can be decomposed into (n \Gamma 1)! node-disjoint paths
of length can be decomposed into (n \Gamma 2)! node-disjoint cycles of length (n \Gamma 1)n. Results
in embedding hypercubes into star networks have been obtained by M. Nigam, S. Sahni, and B.
Krishnamurthy [20] and by Miller, Pritikin, and Sudborough [18]. Broadcasting on star networks
has also been studied recently [3, 4, 14, 23].
Routing on star networks was first studied by Akers and Krishnamurthy [2] who derived a
formula for the length of the shortest path between any two nodes in a star network and developed an
efficient algorithm for constructing such a path. Recently, parallel routing, i.e., constructing node-disjoint
paths, on star networks has received much attention. Sur and Srimni [24] demonstrated
that node-disjoint paths can be constructed between any two nodes in S n in polynomial time.
Dietzfelbinger, Madhavapeddy, and Sudborough [11] derived an improved algorithm that constructs
node-disjoint paths of length bounded by 4 plus the diameter of S n . The algorithm was further
improved by Day and Tripathi [10] who developed an efficient algorithm that constructs
paths of length bounded by 4 plus the distance from u to v in S n . The problem was also
investigated by Jwo, Lakshmivarahan, and Dhall [16]. Misic and Jovanovic [19] derived a general
algebraic expression for all (not necessarily node-disjoint) shortest paths between any two nodes
in S n . Palis and Rajasekaran [21], Dietzfelbinger, Madhavapeddy, and Sudborough [11], Qiu, Akl,
and Meijer [22], and Chen and Chen [9] have considered the problem of node-disjoint paths between
two sets of nodes in a star network.
In this paper, we will improve the previous results on node-to-node parallel routing in star
networks by developing an efficient algorithm that constructs optimal parallel routing between any
two nodes in a star network. More specifically, let u and v be any two nodes in the n-star network
Department of Computer Science and Engineering, Tatung Institute of Technology, Taipei 10451, Taiwan, R.O.C.
Supported in part by Engineering Excellence Award from Texas A&M University. Email: ccchen@cse.ttit.edu.tw.
y Corresponding author. Department of Computer Science, Texas A&M University, College Station,
3112. Supported in part by the National Science Foundation under Grant CCR-9110824. Email: chen@cs.tamu.edu.
S n and let dist(u; v) be the distance from u to v in S n . The bulk length of a group of
node-disjoint paths connecting u and v in S n is defined to be the length of the longest path in the
group. Define the bulk distance Bdist(u; v) between u and v to be the minimum bulk length over
all groups of connecting u and v in S n . We develop an O(n 2 log n) time
algorithm that, given two nodes u and v in S n , constructs a group of node-disjoint paths of
bulk length Bdist(u; v) that connect the nodes u and v in S n .
Our algorithm involves careful analysis on the lower bound on the bulk distance Bdist(u; v)
between two nodes u and v in S n , a non-trivial reduction from the parallel routing problem on star
networks to a combinatorial problem called Partition Matching, a subtle solution to the Partition
Matching problem, and a number of routing algorithms on different kinds of pairs of nodes in a
star network. The basic idea of the algorithm can be roughly described as follows. Let u and v
be two nodes in the n-star network S n . According to Day and Tripathi [10], the bulk distance
Bdist(u; v) is equal to dist(u; v) or 4. We first derive a necessary and sufficient
condition for a pair of nodes u and v to have bulk distance dist(u; 4. For a pair u and v
whose bulk distance is less than dist(u; v) + 4, we develop an efficient algorithm that constructs
a group of node-disjoint paths of bulk length dist(u; v) between u and v. Finally,
an efficient algorithm, which is obtained from a reduction of an efficient algorithm solving the
Partition Matching problem, is developed that constructs the maximum number of node-disjoint
shortest paths (of length dist(u; v)) between u and v. Combining all these analysis and algorithms
gives us an efficient algorithm that constructs an optimal parallel routing on star networks. We
should also point out that the running time of our algorithm is almost optimal (differs at most by
a log n factor) since a lower
running time of parallel routing algorithms on star
networks can be easily derived.
Preliminary
A permutation of the symbols can be given by a product of disjoint cycles
[5], which is called the cycle structure of the permutation. A cycle is nontrivial if it contains more
than one symbol. Otherwise the cycle is trivial. The cycle containing the symbol 1 will be called
the primary cycle in the cycle structure. A -[1; i] transposition on the permutation u is to exchange
the positions of the first symbol and the ith symbol in u: -[1;
It is sometimes more convenient to write the transposition -[1; i](u) on u as -[a i ](u) to indicate
that the transposition exchanges the positions of the first symbol and the symbol a i in u. Let us
consider how a transposition changes the cycle structure of a permutation. Write u in its cycle
structure
If a i is not in the primary cycle, then -[1; i] "merges" the cycle containing a i into the primary
cycle. More precisely, suppose that a (note that each cycle can be cyclically permuted and
the order of the cycles is irrelevant), then the permutation -[1; i](u) will have the following cycle
structure:
If a i is in the primary cycle, then -[1; i] "splits" the primary cycle into two cycles. More precisely,
suppose that a we have let a 1n 1 (note that a
we assume i ? 1), then -[1; i](u) will have the following cycle structure:
In particular, if a then we say that the transposition -[1; i] "deletes" the symbol a 11 from
the primary cycle.
Note that if a symbol a i is in a trivial cycle in the cycle structure of the permutation
a 1 a 1 \Delta \Delta \Delta a n , then the symbol is in its "correct" position, i.e., a that if a symbol is in a
nontrivial cycle, then the symbol is not in its correct position. Denote by " the identity permutation
every symbol is in a trivial cycle.
The n-dimensional star network (or simply the n-star network) S n is an undirected graph
consisting of n! nodes labeled with the n! permutations on symbols There is an edge
between two nodes u and v in S n if and only if there is a transposition -[1; i],
that v. A path from a node u to a node v in the n-star network S n corresponds to
a sequence of applications of the transpositions -[1; i], starting from the permutation
u and ending at the permutation v. A (node-to-node) parallel routing in S n is to construct the
maximum number of node-disjoint paths between two given nodes in S n . Since the n-star network
S n is (n \Gamma 1)-connected [2] and every node in S n is of degree theorem [17], a
parallel routing in S n should produce exactly between two given nodes.
Moreover, since the n-star network is vertex symmetric [2], a parallel routing in the n-star network
any two given nodes can be easily mapped to a parallel routing between a node and
the identity node " in S n . We will write dist(u) and Bdist(u) for the distance dist(u; ") and the
bulk distance Bdist(u; "), resepctively. By the definitions, we always have Bdist(u) - dist(u).
Let u be a node in the n-star network with cycle structure are
nontrivial cycles and e j are trivial cycles. If we further let
denotes the
number of symbols in the cycle c i , then the distance from the node u to the identity node " is given
by the following formula [2].
if the primary cycle is a trivial cycle
if the primary cycle is a nontrivial cycle
Combining this formula with the above discussion on the effect of applying a transposition on a
permutation, we derive the following necessary rules for tracing a shortest path from the node u to
the identity node " in the n-star network S n .
Shortest Path Rules
Rule 1. If the primary cycle is a trivial cycle in u, then in the next node on any shortest
path from u to ", a nontrivial cycle c i is merged into the primary cycle. This corresponds
to applying transposition -[a] to u with a 2 c
Rule 2. If the primary cycle c nontrivial cycle in u,
where a 1n 1 then in the next node on any shortest path from u to ", either a
nontrivial cycle c i 6= c 1 is merged into the primary cycle (this corresponds to applying
transposition -[a] to u, where a 2 c i ), or the symbol a 11 is deleted from the primary
cycle c 1 (this corresponds to applying transposition -[a 12 ] to u).
Fact 2.1. A shortest path from u to " in S n is obtained by a sequence of applications of the
Shortest Path Rules, starting from the permutation u.
Fact 2.2. If a symbol a 6= 1 is in a trivial cycle in u, then a will stay in a trivial cycle in any
node on a shortest path from u to ".
Fact 2.3. If an edge [u; v] in S n does not lead to a shortest path from u to ", then
Consequently, let P be a path from u to " in which exactly k edges do not follow the
Shortest Path Rules, then the length of the path P is equal to dist(u)
Fact 2.4. [10] There are no cycles of odd length in an n-star network. Consequently, the
length of any path from a node u to the node " is equal to dist(u) plus an even number.
Given a node in the n-star network S n , where c i are nontrivial cycles and
e j are trivial cycles, a shortest path from u to " can be constructed through the following two-stage
process:
1. Merge in an arbitrary order each of the nontrivial cycles into the primary cycle. This will
result in a node whose cycle structure has a single nontrivial cycle, which is the primary
cycle. For example, suppose that c
1) is the primary cycle in u and that
by applying the transpositions -[a 21 ], -[a
in this order, we obtain a node with cycle structure
(a k1 \Delta \Delta \Delta a kn k
a
2. Delete each of the symbols in the primary cycle until the node " is reached. For example,
suppose that we start with the node with cycle structure as described in Equation (1), then
we apply the transpositions -[a k2
-[1], in this order, to reach the node ".
The above process will be called the Merge-Delete process. It is easy to verify, using the Shortest
Path Rules, that the Merge-Delete process produces a shortest path from the node u to the node "
in the n-star network S n . The most important property of the Merge-Delete process is that in each
node (except the node ") of the constructed shortest path, the primary cycle is of form
1),
where a 1n 1 is fixed for all nodes on the path.
Parallel routing from a node u to " in S n is particularly simple when the primary cycle in u is a
trivial cycle [10, 16]. For completeness, we describe the routing process for this case here. Let u be
such a node in S n . For each symbol i, 2 - i - n, construct a path P i as follows. The path P i starts
with the edge [u; -[i](u)] followed by a shortest path from the node -[i](u) to ", which is obtained
by applying the Merge-Delete process starting from the node -[i](u). It is easy to verify that if i
is in a nontrivial cycle in u, then the path P i has length dist(u), and that if i is in a trivial cycle
in u then the path P i has length dist(u) 2. On the other hand, if any symbol i, 2 - i - n, is in
a trivial cycle in u, then any path from u to " via -[i](u) has length at least dist(u) 2. Since the
node u has degree any group of node-disjoint paths from u to " contains a path whose
first edge is [u; -[i](u)]. This implies that the bulk distance Bdist(u) is at least dist(u)
is a symbol i in a trivial cycle in u, for 2 - i - n. Therefore, to show that the constructed paths
length Bdist(u), we only need to prove that all these paths are node-disjoint.
In fact, since the first edge on P i is via -[i](u) and the subpath from -[i](u) to " on P i follows the
shortest path obtained by the Merge-Delete process, it is easy to verify that for each path P i , there
is a ng uniquely associated with the path P i such that for each interior node
on the path P i , the primary cycle is of form Therefore, no two of the
P can share a common interior node, and the paths P i , 2 - i - n, are node-disjoint. This gives
a group of node-disjoint paths of bulk length Bdist(u) from u to ".
Therefore, throughout the rest of this paper, we discuss the parallel routing problem in star
networks based on the following assumption:
Assumption 2.1.
The node u in the n-star network S n has cycle structure
are nontrivial cycles and e j are trivial cycles, and the primary cycle c
is a nontrivial cycle.
3 Nodes with bulk distance dist(u)
Day and Tripathi [10] have developed a routing algorithm that constructs
of bulk length dist(u) + 4 from a node u to " in the n-star S n . The basic idea of Day-Tripathi's
algorithm can be described as follows. For each symbol a construct a path P a in
which each node has a cycle of form (\Delta \Delta \Delta a1). This cycle distinguishes the path P a from the other
constructed paths. Let 1), be the node as described in
Assumption 2.1. We describe the path P a in three different cases.
Case 1. The symbol a is in a nontrivial cycle c i , for i ? 1. Without loss of generality, let
a). In this case, the first four nodes on the path P a are u
The rest of the path P a is constructed by applying the Merge-
Delete process, starting from the node u 4 .
Case 2. The symbol a is in a trivial cycle e (a). Then the first four nodes on the path
P a are u the rest of the path P a is
obtained by applying the Merge-Delete process starting from the node u 4 .
Case 3. The symbol a is in the cycle c 1 . Let a = a j , where 1 d. Then the first four nodes
on the path P a are u
simply let u discard the nodes u 1 , u 2 , and u 3 ), and the rest of the path P a is obtained
by applying the Merge-Delete process starting from the node u 4 .
It is easy to verify that in each of the above three cases, the nodes u 2 and u 3 on the path P a are
not contained in any other constructed path P a 0 for a 0 6= a. It is also easy to check that the fourth
node u 4 on the path P a contains a cycle of form the Merge-Delete process keeps
the cycle pattern along the path P a , we conclude that all these
P a , a are node-disjoint. Finally, by examining each constructed path P a , we find out
that at most two edges on P a do not follow the Shortest Path Rules. By Fact 2.3, the path P a has
length at most 4. This completes the description of Day-Tripathi's algorithm.
Combining Day-Tripathi's algorithm and Fact 2.4, we conclude that for any node u in the n-
star network S n , the bulk distance Bdist(u) is equal to dist(u) or 4. In this
section, we derive a necessary and sufficient condition for a node u to have bulk distance dist(u)+4.
Let P be a path in S n from u to ". We say that the path P leaves u with symbol a if the second
node on P is -[a](u), and we say that the path P enters " with symbol a 0 if the node next to the
last node " on P is -[a 0 ]("), which has a single nontrivial cycle (a 0 1).
Lemma 3.1 Let 1), be the node in the n-star network S n as
described in Assumption 2.1. Suppose that m ? minf2
jg. Then any group of
node-disjoint paths from u to " has bulk length at least
Proof. Assume that P 1 node-disjoint paths from u to " of bulk length
bounded by dist(u) 2. We show that in this case we must have
First note that for each symbol b that is in a trivial cycle in u, one of the paths P must
leave u with b, and one of the paths P must enter " with b.
Suppose that a path P i leaves u with a symbol b in a trivial cycle in u. By the Shortest Path
Rules, the node -[b](u) does not lead to a shortest path from u to ". By Fact 2.3,
1. On the other hand, the length of P i is bounded by dist(u) 2. Thus, starting from
the node -[b](u), the path P i must strictly follow the Shortest Path Rules. In particular, no node
on the path P i (including the node -[b](u)) can contain a cycle of form
This implies that the path P i must enter " with a symbol in the set fa d g [ S k
Since there are exactly m of the paths P leaving with symbols in trivial cycles in u, and
since all these paths are node-disjoint and must enter " with symbols in fa d g
that there are at least m different symbols in the set fa d g [
Now again consider the path P i leaving u with a symbol b in a trivial cycle in u. Let u i be the
first node on P i in which the primary cycle is a trivial cycle. Note that u i 6= u and u i 6= -[b](u).
Moreover, since the nontrivial cycles in the node -[b](u) are c 0
and the path P i strictly follows the Shortest Path Rules after the node -[b](u), every nontrivial
cycle in the node u i is a cycle in the set fc g. Therefore, the node u i , hence the path P i ,
corresponds to a subset of the set fc g.
Similarly, suppose that P h is a path among in a
trivial cycle in u. Since at node u, the symbol b is in a trivial cycle while at node -[b](") on the
path P h , the symbol b is in a nontrivial cycle, we can find two consecutive nodes u h and v h on the
path P h such that the symbol b is in a trivial cycle in the node u h while in a nontrivial cycle in the
node v h . By Fact 2.2, the edge [u h ; v h ] on the path P h does not follow the Shortest Path Rules.
By our assumption, the length of the path P h is bounded by dist(u) 2. We conclude that the
subpaths of P h from u to u h and from v h to ", respectively, must strictly follow the Shortest Path
Rules. Note that by our assumption on the nodes u h and v h , we must have and the
symbols b and 1 are in the same cycle in the node v h . Since the node
trivial cycles) is on the subpath of P h from v h to ", in order to let the subpath of P h from v h to " to
strictly follow the Shortest Path Rules, the node v h must have a cycle of form (b 1). Consequently,
the symbol 1 is in a trivial cycle in the node u h . Now since the subpath of P h from u to u h follows
strictly the Shortest Path Rules, every nontrivial cycle in the node u h must be one of the nontrivial
cycles in the node u. This proves that the node u h , thus the path P h , corresponds to a
subset of the set fc g.
As we have shown before, no path in P 1 leave u with a symbol b and enters
" with a symbol b 0 , where b and b 0 are symbols in trivial cycles in the node u. Therefore, there
are exactly 2m paths among leaves u or enters " with a symbol in a
trivial cycle in u. Each of these 2m paths corresponds to a subset in the set fc g. Since all
these paths are node-disjoint, we conclude that there are at least 2m different subsets of the set
g. That is, 2 equivalently, m - 2 k\Gamma2 .
Combined with Day-Tripathi's algorithm, Lemma 3.1 provides a sufficient condition for a node
u in the n-star network S n to have bulk distance 4. In the following, we show that this
condition is also necessary. For this, we demonstrate that when m - minf2 k\Gamma2
can always construct node-disjoint paths from u to " of bulk length dist(u) 2.
We first make some conventions. We assume that n - 3 since the parallel routing on an n-star
network S n for n - 2 is trivial. Let c be a cycle, given in any fixed cyclic order. We will denote by
[c] the sequence of the symbols in the cycle c. Therefore, ([c] a 1 \Delta \Delta \Delta a d ) is a cycle starting with the
symbols in the cycle c followed by the symbols a 1 a d . Recall that a cycle can be arbitrarily
cyclically rotated, still resulting in the same cycle. In many cases, we will discard irrelevant trivial
cycles in a cycle structure.
Let 1), be the node in the n-star network S n as described
in Assumption 2.1, and suppose m - minf2 k\Gamma2
jg. We describe our construction in
three different cases.
Case I. The number k of nontrivial cycles in u is equal to 1.
By the condition Therefore, the cycle structure of the node u
consists of a single (nontrivial) cycle 1). Note that the unique cycle in u contains
at least 3 symbols since n - 3. The node-disjoint paths from u to " are given as follows.
A path P 1 leaving u with a 2 and entering " with a n\Gamma1 is given by
(a 1 a 2 \Delta \Delta \Delta a
stands for a sequence of transpositions that repeatedly deletes a symbol from the
primary cycle.
A path P 2 leaving u with 1 and entering " with a 1 is given by
(a 1 a 2 \Delta \Delta \Delta a
For there is a path P j leaving u with a j and entering " with a j \Gamma1 , given by
It is easy to verify that each path P j , 1, has at most one edge that does not
follow the Shortest Path Rules. Thus, all these constructed paths have length at most dist(u) 2.
The path P 1 keeps a cycle of form 1). The path P 2 keeps a cycle of form 1). For
the first part of the path P j keeps a distinguished cycle (a 1 the second
part of the path P j keeps a cycle of form 1). Therefore, all these constructed paths are
node-disjoint. This gives in this case a group of node-disjoint paths of bulk length bounded
by from u to ".
Case II. The number k of nontrivial cycles in u is at least 2, and the number m of trivial
cycles in u is 0.
In this case, the node u can be written as
A path P 1 leaving u with 1 and entering " with a d is given by
stands for a sequence of transpositions that repeatedly merges a nontrivial cycle
into the primary cycle.
For there is a path P j leaving u with a j and entering " with a j \Gamma1 , given by
Note that this group of paths is constructed only when d - 2.
For each symbol a 2 [ k
there is a path P a leaving u with a and entering " with a. Since
each nontrivial cycle can be cyclically rotated and the order of the cycles c 2
we can assume, without loss of generality, that c path P a is given by
It is again easy to verify that all these are of length at most dist(u)
disjoint. Thus, this gives in this case a group of node-disjoint paths of bulk length bounded
by from u to ".
Case III. The number k of nontrivial cycles in u is at least 2 and the number m of trivial
cycles in u is at least 1.
In this case, the node u can be written as
are nontrivial cycles and (b 1 are trivial cycles.
A path P 1 leaving u with b 1 and entering " with a d is constructed as follows.
A path P 0
leaving u with a 2 and entering " with b 1 is given by
If then the above constructed path
leaves u with the symbol 1 and enters " with b 1 .
For each i, we construct two paths P i and P 0
i as follows. First mark all symbols
in [ k
as "unused", and mark all subsets of the set as "unused". Then for
each pick an unused symbol a 0
and an unused subset S
from the set such that S i 6= S and a 0
i is contained in a cycle in the subset S i . Let
loss of generality, we assume that the cycle c (i)
contains the
leaves u with a 0
i and enters " with b i , and is given by
c (i)
(a d 1)c (i)
and the path P 0
leaves u with b i and enters " with a 0
, and is given by
c (i)
(b
c (i)
Now mark the symbol a 0
i and the subsets fc (i)
and fc (i)
k g of the set fc
as "used".
We must justify that the construction of the paths P i and P 0
i is always possible. Since m -
there are at least
Therefore, for each i,
should always be able to find an unused symbol a 0
Now fix the symbol a 0
. There are
different subsets S 0 of the set such that S 0 6= S and a cycle in S 0 contains
the symbol a 0
at least one of such subsets has not been used for constructing
the previous paths P j and P 0
(note that in the two subsets fc (j)
and
used for the paths P j and P 0
only one of them has a cycle containing the symbol
a 0
Also note that if S 0 is an unused subset of S, then S \Gamma S 0 is also an unused subset of S.
Therefore, we are always able to find an unused subset S i of S such that S i 6= S and a cycle in S i
contains the symbol a 0
i . This ensures the possibility of the construction of the paths P i and P 0
If the cycle c contains more than two symbols, i.e., d - 2, then we also construct
the following
The path Q 2 leaves u with the symbol 1 and enters " with a
and for d, the path Q j leaves u with a j and enters " with a
Finally, for each symbol a in [ k
that is not used in constructing the paths P i and P 0
we construct a path P a leaving u with a and entering " with a. Without loss of
generality, let the symbol a be in the cycle
The above process constructs paths from the node u to ". It is easy to verify that each
of the constructed paths has at most one edge that does not follow the Shortest Path Rules. By
Fact 2.3, all these are of length at most dist(u) 2. What remains is to show that all
these paths are node-disjoint.
On each of the constructed paths, the nodes have a special cycle pattern to ensure that the
path is node-disjoint from the other paths.
1. Path P 1 consists of two parts of different format: each node in the first part has a cycle of
and each node in the second part has a single nontrivial cycle of form
1), where the symbol a d is uniquely associated with the path
2. Path P 0
1 consists of two parts of different format: each node in the first part has a cycle
structure of form and each node in the second part has a cycle of form
where the symbol b 1 is uniquely associated with the path P 0
3. Path P i , consisits of three parts of different format: each node in the first part
has a cycle of form
1), each node in the second part has a cycle structure
of form
, where the subset fc (i)
k g is uniquely associated with the
path and each node in the third part has a cycle of form where the symbol b i is
uniquely associated with the path P i . Note that the assumption S i 6= S is necessary here -
otherwise, the path P i would enter " with the symbol a d and would share a common interior
node with path
Similarly, path P 0
consists of three parts of different format: each node in
the first part has a cycle of form 1), each node in the second part has cycle
structure of form
, where the subset fc (i)
g is uniquely associated with
the path P 0
and each node in the third part has a cycle of form
1), where the symbol
a 0
i is uniquely associated with the path P 0
. Again here the condition S i 6= S is necessary -
otherwise, the third node of the path P 0
i would be the node u again and the path P 0
would
then leave u with the symbol a 2 and share an interior node with the path P 0
1 .
4. The second node of the path Q 2 has a distinguished cycle (a 1 \Delta \Delta \Delta a d ), and the rest of the nodes
in the path Q 2 have a cycle of form (\Delta \Delta \Delta a 1 1), where the symbol a 1 is uniquely associated with
the path
5. The path Q d, consists of two parts of different format: each node in the first
part has a distinguished cycle (a 1 each node in the second part has a cycle of
the symbol a j \Gamma1 is uniquely associated with the path Q
6. For each symbol a that is not used in the paths P i and P 0
m, the second node
in the path P a has a cycle (aa 1), the third node in the path P a has a cycle
and the rest of the nodes in P a have a cycle of form (\Delta \Delta \Delta a1), where the
symbol a is uniquely associated with the path P a .
Therefore, all these constructed paths are node-disjoint. Summarizing all the above
discussions, we obtain the following lemma.
Lemma 3.2 Let 1), be the node in the n-star network S n as
described in Assumption 2.1. If m - minf2 k\Gamma2
a group of
paths of bulk length dist(u) + 2 from u to " can be constructed in time O(n 2 log n).
Proof. The construction of a group of node-disjoint paths of bulk length dist(u) + 2 from
u to " has been given in the above discussion.
For each P of the paths
and P a , where a is a symbol in [ k
is not used in the construction of the paths P i and P 0
m, the construction of P can be
obviously implemented in time O(n). (Note that according to [2],
To construct the paths P i and P 0
i , we need to find an unused symbol a 0
. The symbol a 0
i can be
simply found in time O(n) if we keep a record for each symbol to indicate whether it has been used.
Once the symbol a 0
i is decided, we need to find an unused subset S i of the set g. For
this, suppose that the symbol a 0
i is in cycle c 0 . We pick arbitrarily another
r from the set S (note that by our assumption, log m+ 2 - k). Now instead of using the set S, we
use the set S
r g. Since the set S 0 has
and the cycle c 0 is in S 0 , at least one of these subsets has not been used. These subsets of S 0
can be enumerated in a systematic manner in time O(r2 r log n) since each
such subset contains at most r = O(log m) cycles. Now an unused subset of S 0 is also an unused
subset of S, with which we can construct the paths P i and P 0
i in time O(n). In conclusion, the
paths
i can be constructed in time O(n log n) for each
total time needed to construct the paths P i and P 0
is bounded by O(n 2 log n).
Combining Lemma 3.1 and Lemma 3.2, we obtain immediately the following theorem.
Theorem 3.3 Let 1), be the node in the n-star network S n
as described in Assumption 2.1. The bulk distance Bdist(u) from the node u to the identity node "
is
4 The maximum number of node-disjoint shortest paths
In this section we diverge to a slightly different problem. Let u be the node in the n-star network
S n as described in Assumption 2.1. How many node-disjoint shortest paths (of length dist(u)) can
we find from u to "?
This problem is closely related to a combinatorial problem, called Maximum Partition Matching,
formulated as follows:
be a collection of subsets of the universal set ng
such that S k
partition matching (of order m)
of S consists of two ordered subsets of m
elements of U (the subsets L and R may not be disjoint), together with a sequence of m
distinct partitions of S: such that for all
a i is contained in a subset in the collection A i and b i is contained in a subset in the
collection B i . The Maximum Partition Matching problem is to construct a partition
matching of order m for a given collection S with m maximized.
Theorem 4.1 The Maximum Partition Matching problem is solvable in time O(n 2 log n).
Proof. An O(n 2 log n) time algorithm has been developed in [7] that, given a collection S of
subsets in constructs a maximum partition matching of S. We refer our readers
to [7] (and [6]) for details.
Now we show how Theorem 4.1 can be used to find the maximum number of node-disjoint
shortest paths from a node u to the identity node " in star networks.
Lemma 4.2 Let 1), be the node in the n-star network S n as
described in Assumption 2.1. Then the number of node-disjoint shortest paths from u to " cannot
be larger
Proof. According to Rule 2 of the Shortest Path Rules, only the path leaving u with a symbol
in the set fa 2 g [
can be a shortest path from u to ".
Another upper bound on the number of node-disjoint shortest paths from u to " can be derived
in terms of the maximum partition matching of the collection of nontrivial cycles
in u, where each nontrivial cycle is regarded as a set of symbols.
Lemma 4.3 Let 1), be the node in the n-star network S n as
described in Assumption 2.1. Then the number of node-disjoint shortest paths from u to " cannot
be larger than 2 plus the number of partitions in a maximum partition matching in the collection
g, where the cycles c i are regarded as sets of symbols.
Proof. Let shortest paths from u to ". For each path P i , let u i
be the first node on P i such that in u i the primary cycle is a trivial cycle. The node u i is obtained
by repeatedly applying Rule 2 of the Shortest Path Rules, starting from the node u. It is easy
to prove, by induction, that in any node v on the subpath from u to u i on the path P i , the only
possible nontrivial cycle that is not in fc is the primary cycle. In particular, the node u i
must have a cycle structure of the form
are nontrivial cycles, e 0
are trivial cycles and B
g is a subcollection of the
collection g.
Assume that the path P i leaves u with the symbol b i . By Rule 2 in the Shortest Path Rules,
b i is either a 2 or one of the symbols in [ k
also by this rule, once b i is contained in
the primary cycle in a node in the path P i , it will stay in the primary cycle in the nodes along the
path P i until it is deleted from the primary cycle, i.e., until b i is contained in a trivial cycle. In
particular, the symbol b i is not in the set [ k i
.
Now suppose that the path P i enters the node " with a symbol d i . Thus, the node w
on the path P i must have a cycle structure (d i 1) if we discard trivial cycles in w i . Since the symbol
d i is in a nontrivial cycle in w i , by Fact 2.2, d i is also in a nontrivial cycle in the node u i , that is
. The only exception is d (in this case u
Now we let A . Then we can conclude that except for at most two paths P 1 and P 2 ,
each of the other paths P 3 must leave the node u with a symbol b i in A i and
enter " with a symbol d i in B i . (The two exceptional paths P 1 and P 2 may leave u with the symbol
a 2 or enter " with the symbol a d .)
Now since the s paths are node-disjoint, the symbols b 3 are all pairwise
distinct, and the symbols d 3 are also pairwise distinct. Moreover, since all nodes u
are pairwise distinct, the collections B 3 of cycles are also pairwise distinct. Consequently,
the partitions of the collection together with the symbol
sets partition matching of the collection S.
This concludes that s cannot be larger than 2 plus the number of partitions in a maximum
partition matching of the collection thus proves the lemma.
Now we show how we construct a maximum number of node-disjoint shortest paths from the
node 1), as described in Assumption 2.1, to the identity node
" in the n-star network S n . We first show how to route a single shortest path from u to ", given a
partition (A; B) of the collection g, and a pair of symbols b and d, where b is in a
cycle in A and d is in a cycle in B. We also allow b to be a 2 - in this case d must be in [ k
S. Similarly, we allow d to be a d - in this case b must be in [ k
S. Consider the algorithm Single Routing given in Figure 1. Since the algorithm Single
Routing starts with the node u and applies only transpositions described in the Shortest Path
Rules, we conclude that the algorithm Single Routing constructs a shortest path from the node
u to the node ".
Now we are ready for describing the final algorithm. Consider the algorithm Maximum Shortest
Routing given in Figure 2.
Algorithm. Single Routing
input: A partition (A;B) of and two symbols b and d, where b is in a cycle in A
and d is in a cycle in B. b can be a2 with A = OE, and d can be ad with
output: A shortest path from u to " leaving u with b and entering " with d.
1. if b 6= a2
apply -[b] to u to merge the cycle in A that contains b into the primary cycle c1 ; then merge in
an arbitrary order the rest of the cycles in A into the primary cycle;
2. repeatedly delete symbols in the primary cycle until the primary cycle becomes a trivial cycle;
3. if d 6= ad
suppose that the cycle c containing d in B is Apply -[d 0 ] to merge c into the primary
cycle (1); then merge in an arbitrary order the rest of the cycles in B into the primary cycle;
4. repeatedly delete symbols in the primary cycle until reach the node ";

Figure

1: The algorithm Single Routing
Algorithm. Maximum Shortest Routing
input: The node u in the n-star network Sn , as described in Assumption 2.1.
output: A maximum number of node-disjoint shortest paths from u to ".
1. Construct a maximum partition matching M [(b1 ds )] in ck g with the
partitions
2. if
shortest paths as follows.
2.1. Call the algorithm Single Routing with the partition (OE; S) of S and the symbol
2.2. Call the algorithm Single Routing with the partition (S; OE) of S and the symbol
2.3. For to s, call the algorithm Single Routing with the partition
the symbol pair (b
3. if s !
shortest paths as follows.
3.1. Let b0 ;
3.2. Call the algorithm Single Routing with the partition (OE; S) of S and the symbol
3.3. Call the algorithm Single Routing with the partition (S; OE) of S and the symbol
3.4. For to s, call the algorithm Single Routing with the partition
the symbol pair (b

Figure

2: The algorithm Maximum Shortest Routing
Theorem 4.4 The algorithm Maximum Shortest Routing constructs a maximum number of
node-disjoint shortest paths from the node u to the identity node " in time O(n 2 log n).
Proof. From Lemma 4.2 and Lemma 4.3, we know that the number of shortest paths constructed
by the algorithm Maximum Shortest Routing matches the maximum number of node-disjoint
shortest paths from u to ". What remains is to show that all these paths are node-disjoint.
Suppose that the algorithm Maximum Shortest Routing constructs h shortest paths
h from node u to node ", here depending on whether
suppose that the path P i is constructed by calling the algorithm Single Routing on partition
then we have
then we have d Now fix an i and consider the path P i , which is
constructed from the partition and the symbol pair (b
l g and
g, where if A i 6= OE then the cycle c (i)
2 is of form c (i)
then the cycle c (i)
l+1 is of form c (i)
Finally, recall that the primary cycle c 1 has the form
The interior nodes of the path P i can be split into three segments I (i)
2 , and I (i)
3 . The first
segment I (i)
1 corresponds to nodes constructed in step 1 of the algorithm Single Routing that
first merges cycle c (i)
2 into the primary cycle c 1 , obtaining a cycle of form (b
merges cycles c (i)
l into the primary cycle. Therefore, for all nodes in this segment, the
primary cycle is of the form
The second segment I (i)
2 corresponds to the nodes constructed by step 2 of the algorithm Single
Routing that deletes symbols in the primary cycle. All nodes in this segment are of the form
The third segment I (i)
3 corresponds to the nodes constructed by step 3 and step 4 of the algorithm
Single Routing, which first merges the cycle c (i)
l+1 into the primary cycle (1), obtaining a cycle of
merges the cycles c (i)
k into the primary cycle, and then deletes symbols
in the primary cycle. Therefore, in all nodes in this segment, the primary cycle should have the
In case A and the segment I (i)
1 is empty, and in case
a d and the segment I (i)
3 is empty.
We now show that any two shortest paths P i and P j , i 6= j, constructed by the algorithm
Maximum Shortest Routing are node-disjoint. Let v be a node on the path P i .
Suppose that
is a node on the first segment I (i)
1 of the path P i .
The node cannot be on the first segment I (j)
1 of the path P j since all nodes on I (j)
1 are of form
Moreover, the node v cannot be on the
second or the third segment of P j since the cycle structure of a node on the second or the third
segment of P j has more trivial cycles (note that each execution of step 2 of the algorithm Single
Routing creates a new trivial cycle in the cycle structure).
k is on the second segment I (i)
2 of the path P i , then v cannot be on the
second segment I (j)
of P j since each node on I (j)
2 is of form
k and
The node v can neither be on the third segment I (j)
3 of P j since each node on the segment I (j)
3 is of
while the primary cycle in the node v is either a trivial cycle
or of form (\Delta \Delta \Delta a d 1) where a d is in c 1 .
Finally, if is on the third segment of the path P i , then v cannot be on the third
segment of P j because d i 6= d j .
By symmetry, the above analysis shows that the two shortest paths P i and P j constructed by
the algorithm Maximum Shortest Routing must be node-disjoint.
The running time of the algorithm Maximum Shortest Routing is dominated by step 1
of the algorithm, which takes time O(n 2 log n) according to Theorem 4.1. Thus, the algorithm
Maximum Shortest Routing runs in time O(n 2 log n).
Construction of the maximum number of node-disjoint shortest paths between two nodes in star
networks was previously studied in [16], which presents an algorithm that runs in exponential time
in the worst case. More seriously, the algorithm seems based on an incorrect observation, which
claims that when there are more than one nontrivial cycles in a node u, the maximum number of
node-disjoint shortest paths from u to " is always an even number. Therefore, the algorithm in [16]
always produces an even number of node-disjoint shortest paths from u to ". A counterexample to
this observation has been constructed in [6].
5 Conclusion: an optimal parallel routing
Combining all the previous discussion in the present paper, we obtain an O(n 2 log n) time algorithm,
Optimal Parallel Routing as shown in Figure 3, that constructs node-disjoint paths of
bulk length Bdist(u) from any node u to the identity node " in the n-star network S n .
The correctness of the algorithm Optimal Parallel Routing has been proved by Lemma 3.1,
Lemma 3.2, Theorem 4.4, and the results in [10]. The running time of the algorithm is O(n 2 log n).
We would like to make a few remarks on the complexity of our algorithm. The bulk distance
problem on general graphs is NP-hard [13]. Thus, it is very unlikely that the bulk distance problem
can be solved in time polynomial in the size of the input graph. On the other hand, our algorithm
solves the bulk distance problem in time O(n 2 log n) on the n-star network. Note that the n-star
network has n! nodes. Therefore, the running time of our algorithm is actually a polynomial of the
logarithm of the size of the input star network. Moreover, our algorithm is almost optimal (differs
at most by a log n factor) since the following lower bound can be easily observed - the distance
dist(u) from u to " can be as large as \Theta(n). Thus, constructing node-disjoint paths from u
to " takes time at least \Theta(n 2 ) in the worst case.



--R

The star graph: an attractive alternative to the n-cube
A group-theoretic model for symmetric interconnection networks

A routing and broadcasting scheme on faulty star graphs
A Survey of Modern Algebra
Combinatorial and algebraic methods in star and de Bruijn networks
The maximum partition matching problem with applications
Optimal parallel routing in star networks
An improved one-to-many routing in star networks
A comparative study of topological properties of hypercubes and star graphs
Three disjoint path paradigms in star networks
Short length versions of Menger's theorem
Computers and Intractability: A Guide to the Theory of NP-Completeness
The cost of broadcasting on star graphs and k-ary hypercubes
Embedding of cycles and grides in star graphs
Characterization of node disjoint (par- allel) path in star graphs

Near embeddings of hypercubes into Cayley graphs on the symmetric group
Routing function and deadlock avoidance in a star graph interconnection network
Embedding hamiltonians and hypercubes in star interconnection graphs
Packet routing and PRAM emulation on star graphs and leveled networks
On some properties and algorithms for the star and pancake interconnection networks
An optimal broadcasting algorithm without message redundancy in star graphs
Topological properties of star graphs
--TR

--CTR
Cheng-Nan Lai , Gen-Huey Chen , Dyi-Rong Duh, Constructing One-to-Many Disjoint Paths in Folded Hypercubes, IEEE Transactions on Computers, v.51 n.1, p.33-45, January 2002
Eunseuk Oh , Jianer Chen, On strong Menger-connectivity of star graphs, Discrete Applied Mathematics, v.129 n.2-3, p.499-511, 01 August
Chi-Chang Chen , Jianer Chen, Nearly Optimal One-to-Many Parallel Routing in Star Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1196-1202, December 1997
Adele A. Rescigno, Optimally Balanced Spanning Tree of the Star Network, IEEE Transactions on Computers, v.50 n.1, p.88-91, January 2001
shortest path;parallel routing;star network;partition matching;network routing;graph container