Abstract  The  fact  that  the  demands  which  could  be  labelled  a s  “luxurious”  in  the  past  times,  have  became  requirements  makes  it  inevitable  that  the  service  providers  do  n ew  researches  and  prepare  alternative  plans  under  h arsh  competition  conditions.  In  order  to,  provide  the  customers  with   the  services  in  terms  of  the  committed  standards  b y  taking  the  possible  damages on wired and wireless networks into conside ration. Finding vertex disjoint paths gives many advantages on the wired  or  wireless  communication  especially  on  Ad-Hoc  Netw orks.  In  this  paper,  we  suggest  a  new  algorithm  that  calculates  alternative  routes  which  do  not  contain  common  vert ex  (vertex-disjoint  path)  with  problematic  route  during  a  point-to-point  communication on the network in a short time and it  is compared to similar algorithms.   

References

[1] Abbas A., A Hybrid Protocol for Identification of a Maximal Set of Node Disjoint Paths in Mobile Ad-Hoc Networks, the International Arab Journal of Information Technology , vol. 6, no. 4, pp. 344-358, 2009.

[2] Ben-Asheri Y., Feldman S., and Feldman M., Dynamic Multipath Allocation in Ad Hoc Networks, the Computer Journal , vol. 54, no. 2, pp. 197-212, 2011.

[3] Chang H. and Tassiulas L., Energy Conserving Routing in Wireless Ad-Hoc Networks, in Proceedings of the 19 th Annual Joint Conference of the IEEE Computer and Communications Society , pp. 22-31, 2000.

[4] Chang H. and Tassiulas L., Fast Approximate Algorithms for Maximum LifeTime Routing in Wireless Ad-Hoc Networks, in Proceedings of the European Commission International Conference on Networking Broadband Communications , High Performance Networking , and Performance of Communication Networks , Paris, France, pp. 702-713, 2000.

[5] Chen C. and Chen J., Nearly Optimal One-to- Many Parallel Routing in Star Networks, IEEE Transaction on Parallel and Distributed Systems , vol. 8, no. 12, pp. 1196-1202, 1997.

[6] Cidon I., Rom R., and Shavitt Y., Analysis of Multi-Path Routing, IEEE/ACM Transactions on Networking , vol. 7, no. 6, pp. 885-896, 1999.

[7] Cormen H., Leiserson E., Rivest L. and Stein C., Introduction to Algorithms , MIT Press, 2001.

[8] Eppstein D., Finding the k Shortest Path, in Proceedings of the 35 th Annual Symposium on Foundation of Computer Science , New Mexico, USA, pp. 154-165, 1994.

[9] Fu S., Chen H. and Duh R., Node-Disjoint Paths and Related Problems on Hierarchical Cubic Networks, Networks, vol. 40, no. 3, pp. 142- 154, 2002.

[10] Fujita S., Polynomial Time Algorithm for Constructing Vertex-Disjoint Paths in Transposition Graphs, Networks , vol. 56, no. 2, pp. 149-157, 2010. FFDisjPath MebDisjPath FFDisjPath MebDisjPath FFDisjPath MebDisjPath FFDisjPath MebDisjPath FFDisjPath MebDisjPath A New Algorithm for Finding Vertex-Disjoint Paths 555

[11] Gu P. and Peng S., Node-to-Set Disjoint Paths Problem in Star Graphs, Information Processing Letters , vol. 62, no. 4, pp. 201-207, 1997.

[12] Guo Y., Kuipers F., and Van Mieghem P., Link- Disjoint Paths for Reliable Qos Routing, the International Journal of Communications Systems , vol. 16, no. 9, pp. 779-798, 2003.

[13] Gurski F. and Wanke E., Vertex Disjoint Paths on Clique-Width Bounded Graphs, Theoretical Computer Science , vol. 359, no. 1, pp. 188-199, 2006.

[14] Kang I. and Poovendran R., Maximizing Static Network Lifetime of Wireless Broadcast Ad-Hoc Networks, in Proceedings of International Conference on Communication , Alaska, USA, pp. 2256-2261, 2003.

[15] Liang W. and Liu Y., On-Line Disjoint Path Routing for Network Capacity maximization in Energy-Constrained Ad-Hoc Networks, Ad-Hoc Networks , vol. 5, no. 2, pp. 272-285, 2007.

[16] Lin C. and Duh R., Constructing Vertex- Disjoint Paths in (n,k)-Star Graphs, Information Sciences , vol. 178, no. 3, pp. 788-801, 2008.

[17] Natarajan S. and Sprague P., Disjoint Paths in Circular Arc Graphs, Nordic Journal of Computing , vol. 3, no. 3, pp. 256-270, 1996.

[18] Sesay S., Yang Z., and He A., Survey on Mobile Ad-Hoc Wireless Network, Information Technology Journal , vol. 3, no. 2, pp. 168-175., 2004.

[19] Sidhu D., Nairand R., and Abdallah S., Finding Disjoint Paths in Networks, ACM SIGCOMM Computer Communication Review , vol. 21, no. 4, pp. 43-51, 1991.

[20] Sidhu P., Abdauah S., and Nair R., A Distance Vector Algorithm for Aletnate Path Routing, Technical Report , University of Maryland, 1990. Mehmet Kurt assistant professor received his BE, ME and PhD degrees in mathematics and computer science from Ege University in 2000, 2004 and 2010. Currently, he is with mathematics and computer science, Izmir University, Turkey. He research interests include graph theory, computer networks and algorithms. Murat Berberler received his BE, ME, PhD degrees in mathematics and computer science from Ege University in 2003, 2006 and 2009. Currently, he is with school of computer science, Dokuz Eylul University, Turkey. He research interests include computer networks, design and analysis of algorithms and mathematical modeling. Onur Ugurlu received his BE degree in mathematics in 2011. Currently, he is is the ME degree candidate with school of computer science, Ege University, Turkey. His research interests include artificial intelligence and graph theory.