 Wireless Sensor Network, 2011, 3, 384-390 doi:10.4236/wsn.2011.312045 Published Online December 2011 (http://www.SciRP.org/journal/wsn) Copyright © 2011 SciRes. 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 E-mail: kejiazhang.hit@gmail.com, honggao@hit.edu.cn 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 vuVV }. 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. Copyright © 2011 SciRes. WSN
 K. J. ZHANG ET AL. 386 st a b c d e f 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 Copyright © 2011 SciRes. WSN
 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 . Copyright © 2011 SciRes. WSN
 K. J. ZHANG ET AL. Copyright © 2011 SciRes. WSN 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 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 Copyright © 2011 SciRes. WSN
 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. Copyright © 2011 SciRes. WSN
|