Wireless Sensor Network, 2011, 3, 384-390
doi:10.4236/wsn.2011.312045 Published Online December 2011 (http://www.SciRP.org/journal/wsn)
Finding Multiple Length-Bounded Disjoint Paths
in Wireless Sensor Networks
Kejia Zhang, Hong Gao
School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China
Received September 15, 2011; revised October 21, 2011; accepted November 24, 2011
Abstract
In a wireless sensor network, routing messages between two nodes s and t with multiple disjoint paths will
increase the throughput, robustness and load balance of the network. The existing researches focus on find-
ing multiple disjoint paths connecting s and t efficiently, but they do not consider length constraint of the
paths. A too long path will be useless because of high latency and high packet loss rate. This paper deals
with such a problem: given two nodes s and t in a sensor network, finding as many as possible disjoint paths
connecting s and t whose lengths are no more than L, where L is the length bound set by the users. By now,
we know that this problem is not only NP hard but also APX complete [1,2], which means that there is no
PTAS for this problem. To the best of our knowledge, there is only one heuristic algorithm proposed for this
problem [3], and it is not suitable for sensor network because it processes in a centralized way. This paper
proposes an efficient distributed algorithm for this problem. By processing in a distributed way, the algo-
rithm is very communication efficient. Simulation results show that our algorithm outperforms the existing
algorithm in both aspects of found path number and communication efficiency.
Keywords: Disjoint Paths, Sensor Networks, Length-Bounded Paths
1. Introduction
A typical Wireless Sensor Network (WSN) comprises of
thousands of small sensor nodes deployed in the moni-
toring area. Since communication range of sensor node is
very limited, most of data transmissions in WSN need to
be forwarded by many intermediate nodes. Usually, sen-
sor nodes are battery-powered and it is unrealistic to re-
place their batteries, so saving energy is the main object-
ive of WSN design. Researches [4,5] show that the en-
ergy consumption of sending and receiving data is sev-
eral orders of magnitude higher than the energy con-
sumption of computing. Therefore, how to design effi-
cient routing strategies becomes a key issue in WSN. In
recent years, routing with multiple disjoint paths has
been more and more widely studied [6-13]. For two
nodes s and t in the network, a path connecting s and t is
a s - t path. A set of s - t paths are disjoint paths if any
two of them do not any common nodes besides s and t.
The problem studied in this paper is:
Problem. In a WSN, given two nodes s and t and a
user-specified length bound L, find as many as possible
disjoint s - t paths whose length ≤ L.
There are several motivations for routing through mul-
tiple disjoint paths in WSNs. Routing several data pack-
ets through multiple disjoint paths simultaneously will
increase the throughput between the given node pair
dramatically. Since link and node failures are very com-
mon in WSNs, messages can easily be lost while they are
routed through a single path. We can increase reliability
by sending messages redundantly through multiple dis-
joint paths. On the other hand, routing messages often
through a single fixed path would use up the energy of
the nodes in the path quickly. By routing messages
through several disjoint paths alternately, the network
can gain a better balanced load. Moreover, in some ap-
plications, a sensitive message can easily be captured by
eavesdropping nodes while it is routed through a single
path. However, if we break the sensitive message into
small pieces and send these pieces through multiple dis-
joint paths, the task of capturing the whole message
would be much more difficult.
It is necessary to limit the length of the paths. If two
nodes send messages to each other through a too long
path, the transmission latency is likely to be unbearable
for the users. In addition, since each wireless link has a

385 K. J. ZHANG ET AL.
certain amount of packet loss rate, packets have little
chance to reach their destination if they are routed
through a too long path.
The problem studied by this paper has been proved not
only NP-hard but also APX-complete [1,2], which means
that there is no Polynomial Time Approximation Scheme
(PTAS) for it. To the best of our knowledge, in addition
to a heuristic centralized algorithm [3], no other algo-
rithms have been proposed for this problem by now. The
algorithm in [3] is not suitable for WSNs because of high
communication cost. This paper proposes a distributed
algorithm for this problem. Simulation results show that
our algorithm outperforms the existing algorithm in both
aspects of found path number and communication effi-
ciency.
The problem we consider uses the simple path length
(the number of the links in the path) as the metric of the
paths. Sometimes, we have to consider a more compli-
cated path metric. For example, we assume that each link
has a delivery ratio and use the product of per-link deliv-
ery ratios as the metric of a path, which is the delivery
ratio of the path. The algorithm proposed in this paper
can be easily extended to this situation by setting each
edge a weight and using the product of per-edge weights
as path metric.
The remainder of the paper is organized as follows:
Some related works are introduced in Section 2. After
giving preliminary definitions in Section 3, we describe
the proposed distributed algorithm in Section 4. Simula-
tion results which confirm the proposed algorithm's effi-
ciency are given in Section 5. Finally, we conclude the
paper in Section 6.
2. Related Works
In graph theory, there are several researches that study
the problem of finding multiple disjoint s - t paths with
length constraint. Reference [1] proves that this problem
is NP-hard when L ≥ 5. Reference [2] further proves that
this problem is APX-complete when L ≥ 5, so there is no
PTAS for this problem and it will be very hard to give an
approximation algorithm with constant approximation
ratio. Therefore, in addition to the heuristic algorithm in
[3], no other algorithms are proposed for this problem.
The algorithm in [3] is a centralized algorithm which can
output optimal solution when L ≤ 4. If we use it in WSNs,
we have to collect the topology information of the whole
network to the sink node. The communication cost of
such an operation is unbearable for WSNs.
In network area, there are many researches study the
problem of finding multiple disjoint s - t paths. References
[11,14] propose algorithms to find 2 disjoint s - t paths.
References [6,8-10,12,13,15] give efficient distributed
algorithms to find k disjoint s - t paths in the given net-
work, where k is a positive integer set by the users. These
algorithms have the same basic idea: find a s - t path and
delete the nodes in the path, then find the next s - t path
and delete its path nodes, until finding k disjoint paths.
These works have a common disadvantage: they do not
consider the length constraint of the paths. Some paths
they found will be not suitable for transmitting data be-
tween s and t because of high latency and high packet
loss rate.
Some centralized algorithms [7,16-19] are also pro-
posed for finding k disjoint s - t paths. The algorithms in
[7,16,19] can find k disjoint paths with minimum total
length. However, they can also output some too long
paths which are not suitable for routing data. Moreover,
since they process in a centralized way, they are not
suitable for WSNs.
So far, in addition to the algorithm in [3], all the algo-
rithms for finding disjoint s - t paths do not consider
length constraint of paths. The algorithm in [3] is not
applicable in WSNs since it is a centralized algorithm.
Therefore, this paper propose an efficient distributed alg-
orithm for finding disjoint s - t paths with length con-
straint. Simulation results show that our algorithm is
much better than the algorithm in [3] in both aspects of
found path number and communication cost.
3. Preliminaries
We use a graph G = (V, E) to denote the given sensor
network, where V={v | v is a sensor node} and E = {(u, v)
there is a wireless link between and vuVV

}.
When the algorithm executes, it constructs a tree Ts
rooted at s and a tree Tt rooted at t. For each node v in Ts:
its parent in Ts is denoted by parents(v); its s-origin is its
ancestor in Ts who is child of s, and we use origins(v) to
denote it; diss(v) is the length of the path from s to v in Ts.
For each node v in Tt : its parent is parentt(v); its t-origin
is its ancestor in Tt who is child of t, and we use origint(v)
to denote it; dist(v) is the distance from t to v in Tt. Sup-
pose that the algorithm constructs Ts and Tt as shown in
Figure 1. For node g: diss(g) = 4, dist(g) = 4, origins(g) =
a, origint(g) = d. For node h: diss(h) = 4, dist(h) = 4, ori-
gins(h) = b, origint(h) = d.
If v is a node in both Ts and Tt, we say that v is an in-
tersecting node of Ts and Tt. In the example of Figure 1,
g, h, i, j, k are intersecting nodes of Ts and Tt.
For two nodes u and v in Ts, we use uTsv to denote the
path connecting u and v in Ts. For two paths P1 and P2
with a common end node, we use P1 + P2 to denote their
concatenation.

K. J. ZHANG ET AL.
386
st
a
b
c
d
e
f
g
h
i
j
k
Figure 1. Ts and Tt constructed by the algorithm (the solid
lines denote the edges in Ts and the dashed lines denote the
edges in Tt).
4. Distributed Algorithm
The proposed algorithm bases on such an observation: In
a WSN, whether two nodes can communicate with each
other is mainly determined by the physical distance be-
tween the two nodes. If the nodes in a WSN distribute
evenly, the areas near s and t are usually the bottle necks
of the existence of multiple disjoint s - t paths, i.e., the
number of disjoint s - t paths is usually constrained by
the number of the neighbors of s and t.
There are 3 steps in the algorithm. In Step 1, we con-
struct trees Ts and Tt rooted at s and t respectively. The
construction of the trees ends at their intersecting nodes.
In Step 2, some information of the intersecting nodes is
collected to s. The information reveals how Ts and Tt
intersect with each other. In Step 3, s computes an opti-
mal solution with the collected intersecting information.
According to the solution, multiple disjoint s - t paths are
built along the two trees.
4.1. Building Trees
In this step, we build trees Ts and Tt rooted at s and t re-
spectively. The two trees are constructed simultaneously.
In the process of tree construction, each node v in Ts re-
cords the following information: parents(v), origins(v)
and diss(v). Similarly, each node v in Tt records the fol-
lowing information: parentt(v), origint(v) and dist(v).
The construction of Ts/Tt starts at s/t, then gradually
extends outward. Use the construction of Ts as an exam-
ple: At first, s broadcasts an initialization message. Each
node receiving the initialization message joins Ts as a
child of s. Each new node v in Ts broadcasts a Build-Tree
message including its ID, origins(v) and diss(v), so the
neighbors of v can join Ts as v’s children.
The construction of Ts ends at: 1) the intersecting
nodes of Ts and Tt; 2) the node v in Ts such that diss(v) ≥
L. Similarly, the construction of Tt ends at: 1) the inter-
secting nodes of Ts and Tt; 2) the node v in Tt such that
dist(v) ≥ L.
For finding more paths, we hope that the trees are built
evenly. For instance, if s has children a, b, c in Ts, we
hope that the sets of the nodes whose s-origin is a, b, c
respectively have the same size. For this reason, we de-
sign a build-tree delaying mechanism. Use the construc-
tion of Ts as an example: when node v who is not in Ts
receives a Build-Tree message for the first time (the
sender of the message is u), v randomly delays for a
while to receive more Build-Tree messages rather than
joins Ts as u’s child immediately. The range of random
delay is determined by the current distance from s to v in
Ts, i.e., diss(u) + 1. The greater the distance is the greater
the maximum delay time is. During the delay, v records
every Build-Tree message it receives. Suppose that v
receives 4 Build-Tree messages during the delay and the
sender of these messages are u1, u2, u3, u4 respectively.
Let the s-origins of u1, u2, u3, u4 be a, b, b, c respectively.
When the delay ends, v randomly chooses one of { u1, u2,
u3, u4} as its parent so that Pr{origins(v) = a} =
Pr{origins (v) = b} = Pr{origins(v) = c}, where Pr{ori-
gins (v) = a} is the probability that v's s-origin is a.
Algorithm 1: Building Ts
1. if v is a neighbor of s then
2. parents(v) = s, origins(v) = v, diss(v) = 1;
3. Broadcast Build-Tree message {v, origins(v),
diss(v)};
4. else
5. if v receives a Build-Tree message {u, origins(u),
diss(u)}then
6. Record u as a potential parent;
7. if it is v’s first time to receive a Build-Tree
message then
8. Randomly delay for a while according to
diss(u) + 1;
9. if the delay ends then
/* Suppose that v’ potential parents come from
n different s-origins a1, …, an */
10. Randomly choose a potential parent w so that
Pr{origins(v)=a1} =…= Pr{origins(v) = an};
11. parents(v) = w, origins(v) = origins(w),
diss(v) = diss(w) + 1;
12. if v is not in Tt and diss(v) < L then
13. Broadcast a Build-Tree message
{v, origins(v), diss(v)};
The algorithm of building trees is given by Algorithm 1.
In Algorithm 1, we only give the pseudo-codes for
building Ts. The pseudo-codes for building Tt can be

387 K. J. ZHANG ET AL.
gotten from it. The whole process starts by s broadcast-
ing an initialization message. The nodes who receive the
initialization message join Ts as children of s (Line 1 - 3
in Algorithm 1). If node v receives a Build-Tree message
for the first time, it randomly delays for a while accord-
ing its current distance to s in Ts (Line 7 - 8 in Algorithm
1). During the delay, for each Build-Tree message {u,
origins(u), diss(u)} received by v, v records the sender u
as its potential parent (Line 5 - 6 in Algorithm 1). Sup-
pose that the potential parents of v come from n different
s-origins a1, ···, an. When the delay ends, v randomly
chooses a potential parent as its parent so that
Pr{origins(v) = a1}= ··· = Pr{origins(v) = an} (Line 9 - 12
in Algorithm 1). The building of Ts ends at: 1) the inter-
secting nodes of Ts and Tt; 2) the node v in Ts such that
diss(v) ≥ L (Line 13 - 14 in Algorithm 1).
4.2. Collecting Intersecting Information
At the end of Step 1, every intersecting node v checks
whether diss(v)+dist(v)≤ L. If so, we can get a path meet-
ing the length constraint by concatenating path sTsv and
path vTtt, so v sends the intersecting information {ori-
gins(v), origint(v)} to s along Ts. The intersecting infor-
mation indicates that the path we found goes through s's
neighbor origins(v) and t’s neighbor origint(v). When
relaying the intersecting information, each ancestor of v
records the information and its sender. The whole proc-
ess of this step is given by Algorithm 2.
Algorithm 2: Collecting Intersecting Information
1. for each intersecting node v do
2. if diss(v) + dist(v) ≤ L then
3. Send the intersecting information
{origins(v), origint(v)} to parents(v);
4. for each node v in Ts do
5. if receive intersecting information
{origins(v), origint(v)} then
6. Records the information and its sender;
7. Send the information to parents(v);
In an example, the users set the length bound as L = 8.
The algorithm builds Ts and Tt in the given network as
shown in Figure 1. In Step 2, the intersecting node g
sends the intersecting information {a, d} to s along Ts. In
the same way, h, i, j, k respectively send the intersecting
information {b, d}, {b, e}, {b, f}, {c, f} to s along Ts.
4.3. Finding Disjoint Paths
Before introducing Step 3, we give a proposition, which
can easily be gotten by the nature of Ts and Tt.
Proposition 1. For two intersecting nodes v1 and v2, if
origins(v1) ≠ origins(v2) and origint(v1) ≠ origint(v2), then
P1 = sTsv1 + v1Ttt and P2 = sTsv2 + v2Ttt are two disjoint
paths in the network.
Algorithm 3: Finding Disjoint Paths
/* Pseudo-codes for s */
1. Builds a graph


***
,GVE
*
E
, where = {all the
*
V
neighbors of s and t}, ;
2. for each received intersecting information
{origins(v), origint(v)} do
3. **
EE

{origins(v), origint(v)};
4. Find the maximum matching in ;
*
G
5. for each edge (origins(v), origint(v)) in the maximum
matching do
6. Send a Build-Path message to v to
build path;
This step is given by Algorithm 3. At first, s builds a
bipartite graph G* with empty edge set (Line 1 in Algo-
rithm 3). One partite set of G* contains all the neighbors
of s. The other partite set of G* contains all the neighbors
of t. If s receives an intersecting information {origins(v),
origint(v)}, it adds an edge in G* connecting origins(v)
and origint(v) (Line 2 - 3 in Algorithm 3). According to
Proposition 1, we know that each matching in G* denotes
a set of disjoint s - t paths in the network. After receiving
all the intersecting information, s searches for the maxi-
mum matching in G* with existing algorithm (Line 4 in
Algorithm 3), like the algorithm in [20]. For each edge
(origins(v), origint(v)) in the maximum matching, s sends
a Build-Path message to v to construct a path from s to t
(Line 5-6 in Algorithm 3). The Build-Path message is
forwarded to v along Ts. Meanwhile, sTsv is added to the
path. After receiving this message, v sends a Build-Path
message to t along Tt. In this process, vTtt is added to the
path.
In the example shown by Figure 1, after receiving the
intersecting information, s builds a bipartite graph G* as
shown in Figure 2(a). In G*, s finds the maximum mat-
ching as shown in Figure 2(b) with existing algorithm.
Since g, i, k are the sources of the intersecting information
a
b
c
d
e
f
a
b
c
d
e
f
(a) (b)
Figure 2. The constructed G* an d the ma ximum mat ching in it .

K. J. ZHANG ET AL.
388
(a, d), (b, e), (c, f), s sends Build-Path messages to g, i, k
along Ts. After receiving these messages, g, i, k send
Build-Path messages to t along Tt. At the end, 3 disjoint
s - t paths as shown in Figure 3 are built in the network.
the network; find the shortest s - t path in the remaining
network and delete its path nodes. The iteration is exe-
cuted until the length of the found path is greater than L.
The efficiency of an algorithm is measured in two as-
pects: 1) the number of the paths found by the algorithm;
2) the communication cost of the algorithm, i.e., the av-
erage bytes sent and received per node. To get each data
in the simulation results, we did 10 groups of experi-
ments. In each group of experiments: the node locations
are regenerated; the ID of s and t are 1 and 1000 respec-
tively; we compare the 3 algorithms with the changes of
L (L = 10, 20, 30, 40, 50). The simulation results are
given by Figures 4(a) and (b). Each data in the figures is
the average of the results of the 10 groups.
5. Simulation Results
We use a simulator written in C++ codes to evaluate the
efficiency of the algorithm. In the simulation, we deploy
1000 nodes in a 1000 m × 1000 m area. The locations of
the nodes are generated randomly. The transmitting ra-
dius of each node is set to 50 m. In MAC layer, we apply
CSMA/CA mechanism to avoid signal conflicts. In ap-
plication layer, the header of each data packet contains 4
bytes to denote the destination’s ID, the sender’s ID, the
length and the type of the packet. Each receiving and
timer-fire event is added a time stamp and put into a heap.
The events in the heap are executed in the order of their
time stamps. In this way, we can simulate the parallel
processing of the nodes.
With the changes of L, the numbers of the paths found
by the 3 algorithms are as shown in Figure 4(a). We can
see that EDA has the best performance among these 3
algorithms in the aspect of found path number. Naive has
the poorest performance because it searches for paths in
a greedy way and does not consider the possibility of
finding multiple paths. EDA finds more paths because it
builds tree in a balanced way and adopts an optimal
searching strategy.
We compare our Efficient Distributed Algorithm (de-
noted by EDA) with the Heuristic Centralized Algorithm
in [13] (denoted by HCA) and a Naive algorithm. The
basic idea of the Naive algorithm is: find the shortest s - t
path in the network; remove the nodes in the path from
With the changes of L, the communication costs of the
3 algorithms are as shown in Figure 4(b). We can see
that EDA are much better in the aspect of communica-
tion cost compared to HCA and Naive. The communica-
tion cost of HCA is great and steady because HCA col-
lects the topology information of the whole network no
matter what value L is. Naive searches for path repeat-
edly. In each searching, all the nodes in the network ex-
change messages to find the shortest path, so the com-
munication cost of Naive rises with finding more paths.
Since EDA processes in a distributed way and exchange
message once, it is the most efficient one in the 3 algo-
rithms.
st
a
b
c
d
e
f
g
i
k
Overall, the algorithm EDA is better than the algo-
rithm HCA and the Naïve algorithm in both aspects of
found path number and communication cost.
Figure 3. The 3 disjoint paths built by the algorithm.
10 20 30 40 50
0
1
2
3
4
5
6
7
Number of Found Paths
L
Naive
EDA
HCA
10 20 30 40 50
0
50
100
150
200
250
300
350
400
Communication Cost
L
Naive
EDA
HCA
(a) (b)
Figure 4. The simulation results.

389 K. J. ZHANG ET AL.
6. Conclusions
In this paper, we study the following problem: in a sen-
sor network, given two nodes s and t; a user-specified
length bound L, find as many as possible disjoint s - t
paths whose lengths are no more than L. The existing
algorithms for finding multiple disjoint paths rarely con-
sider the length constraint of the paths. For finding mul-
tiple length-bounded disjoint paths, there is only one
heuristic centralized algorithm. In this paper, we propose
an efficient distributed algorithm for this problem. The
simulation results show that our algorithm outperforms
the existing algorithm in both aspects of found path
number and communication cost.
7. Acknowledgements
This work is supported by Key Program of the National
Natural Science Foundation of China (Grand No.
61033015), the National Natural Science Foundation of
China (Grant No. 60831160525), the National Natural
Science Foundation of China (Grant No. 60933001) and
the National Natural Science Foundation of China (Grant
No. 61100030).
8. References
[1] A. Bley, “On the Complexity of Vertex-Disjoint Length-
Restricted Path Problems,” Computational Complexity,
Vol. 12, No. 3, 2003, pp. 131-149.
doi:10.1007/s00037-003-0179-6
[2] D. Ronen and Y. Perl, “Heuristics for Finding a Maxi-
mum Number of Disjoint Bounded Paths,” Networks, Vol.
14, No. 4, 1984, pp. 531-544.
doi:10.1002/net.3230140405
[3] K. Ishida, Y. Kakuda and T. Kikuno, “A Routing Proto-
col for Finding Two Node-Disjoint Paths in Computer
Networks,” Proceedings of 1995 International Confer-
ence on Network Protocols, Tokyo, 7-10 November 1995,
pp. 340-347. doi:10.1109/ICNP.1995.524850
[4] V. Shnayder, M. Hempstead, B. Chen, G. W. Allen and
M. Welsh, “Simulating the Power Consumption of Large-
Scale Sensor Network Applications,” Proceedings of the
2nd International Conference on Embedded Networked
Sensor Systems, Baltimore, 3-5 November 2004, pp. 188-
200.
[5] P. Gupta and P. Kumar, “The Capacity of Wireless Net-
works,” IEEE Transactions on Information Theory, Vol.
46, No. 2, 2000, pp. 388-404. doi:10.1109/18.825799
[6] D. Ganesan, R. Govindan, S. Shenker and D. Estrin,
“Highlyresilient, Energy-Efficient Multipath Routing in
Wireless Sensor Networks,” ACM SIGMOBILE Mobile
Computing and Communications Review, Vol. 5, No. 4,
2001, pp. 11-25. doi:10.1145/509506.509514
[7] A. Srinivas, G. Theory and E. Modiano, “Minimum En-
ergy Disjoint Path Routing in Wireless Ad-Hoc Net-
works,” Proceedings of the 9th Annual International
Conference on Mobile Computing and Networking, San
Diego, 14-19 September 2003, pp. 122-133.
doi:10.1145/938985.938999
[8] S. Li and Z. Wu, “Node-Disjoint Parallel Multi-Path
Routing in Wireless Sensor Networks,” The 2nd Interna-
tional Conference on Embedded Software and Systems,
Xi’an, 16-18 December 2005. p. 6.
[9] J. W. Baek, Y. J. Nam and D. W. Seo, “An Energyeffi-
cient k-Disjoint-Path Routing Algorithm for Reliable
Wireless Sensor Networks,” Software Technologies for
Embedded and Ubiquitous Systems of Lecture Notes in
Computer Science, Vol. 4761, 2007, pp. 399-408.
doi:10.1007/978-3-540-75664-4_42
[10] B. Deb, S. Bhatnagar and B. Nath, “Reinform: Reliable
Information Forwarding Using Multiple Paths in Sensor
Networks,” Proceedings of 28th Annual IEEE Interna-
tional Conference on Local Computer Networks, Bonn/
Königswinter, 20-24 October 2003, pp. 406-415.
doi:10.1109/LCN.2003.1243166
[11] R. Ogier, V. Rutenburg and N. Shacham, “Distributed
Algorithms for Computing Shortest Pairs of Disjoint
Paths, ” IEEE Transactions on Information Theory, Vol.
39, No. 2, 1993, PP. 443-455.
[12] Y. Chen, X. Guo, Q. Zeng and G. Chen, “AMR: A Mul-
tipath Routing Algorithm Based on Maximum Flow in
Ad-Hoc Networks,” Acta Electronica Sinica, Vol. 32, No.
8, 2004, pp. 1297-1301.
[13] X. Fang, S. Shi and J. Li, “A Disjoint Multi-Path Routing
Algorithm in Wireless Sensor Network,” Journal of
Computer Research and Development, Vol. 46, No. 12,
2009, pp. 2053-2061.
[14] A. Itai, Y. Perl and Y. Shiloach, “The Complexity of
Finding Maximum Disjoint Paths with Length Con-
straints,” Networks, Vol. 12, No. 3, 1982, pp. 277-286.
doi:10.1002/net.3230120306
[15] D. Sidhu, R. Nair and S. Abdallah, “Finding Disjoint
Paths in Networks,” SIGCOMM Computer Communica-
tion Review, Vol. 21, No. 4, 1991, pp. 43-51.
doi:10.1145/115994.115998
[16] R. Bhandari, “Optimal Physical Diversity Algorithms and
Survivable Networks,” Proceedings of the 2nd IEEE
Symposium on Computers and Communications, Alexan-
dria, 1-3 July 1997, pp. 433-441.
doi:10.1109/ISCC.1997.616037
[17] S. Khuller and B. Schieber, “Efficient Parallel Algo-
rithms for Testing Connectivity and Finding Disjoint s - t
Paths in Graphs,” Proceedings of the 30th Annual Sym-
posium on Foundations of Computer Science, Research
Triangle Park, 30 October - 1 November 1989, pp. 288-
293. doi:10.1109/SFCS.1989.63492
[18] K. Iwama, C. Iwamoto and T. Ohsawa, “A Faster Parallel
Algorithm for k-Connectivity,” Information Processing
Letters, Vol. 61, No. 5, 1997, pp. 265-269.
doi:10.1016/S0020-0190(97)00015-X

K. J. ZHANG ET AL.
390
[19] J. W. Suurballe, “Disjoint Paths in a Network,” Netw o r ks,
Vol. 4, No. 2, 1974, pp. 125-145.
doi:10.1002/net.3230040204
[20] J. Edmonds, “Paths, Trees and Flowers,” Canadian Jour-
nal of mathematics, Vol. 17, No. 3, 1965, pp. 449-467.