Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming

Print
PDF
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 54 - Number 1
Year of Publication: 2012
Authors:
Nuha A. S. Alwan
Ibraheem K. Ibraheem
Sabreen M. Shukr
10.5120/8531-2063

Nuha A S Alwan, Ibraheem K Ibraheem and Sabreen M Shukr. Article: Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming. International Journal of Computer Applications 54(1):21-26, September 2012. Full text available. BibTeX

@article{key:article,
	author = {Nuha A. S. Alwan and Ibraheem K. Ibraheem and Sabreen M. Shukr},
	title = {Article: Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {54},
	number = {1},
	pages = {21-26},
	month = {September},
	note = {Full text available}
}

Abstract

A systolic parallel system based on simultaneous forward and backward dynamic programming is proposed for the solution of the shortest path problem. The speed-up advantage of this fast systolic solution to this problem is very important in applications such as shortest-path routing in wireless networks for instance. The merit of this method becomes clear in a straightforward manner when the number of stages of the directed acyclic graph (DAG) through which the shortest path is derived is odd, although an even number of stages can also be accounted for.

References

  • Sedgewick, R. , Wayne, K. 2011. Algorithms. Fourth edition, Addison-Wesley, Upper Saddle River, NJ.
  • Stallings, W. 2011. Data and Computer Communications. Ninth edition, Pearson.
  • Glisic, S. , Lorenzo, B. 2009. Advanced Wireless Networks. Second edition, Wiley.
  • Hong, K. S. , Choi, L. 2010. DAG-Based Multipath Routing for Mobile Sensor Networks. Online: http://it. korea. ac. kr /research/publication/papers/DMR-ICTC2011. pdf.
  • Dasgupta, S. , Papadimitriou, C. , Vazirani, U. 2007. Algorithms. McGraw-Hill.
  • Gansner, E. R. , Koutsofios, E. , North, S. C. , Vo, K. P. 1993. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, vol. 19, no. 3, March, 1993. 214-230.
  • Elmallah, E. S. , Culberson, J. 1995. Multicommodity Flows in Simple Multistage Networks. Networks, vol. 25. 19-30.
  • Moon, T. K. , Stirling, W. C. 2000. Mathematical Methods and Algorithms for Signal Processing. Upper Saddle River, New Jersey: Prentice-Hall.
  • Doerr, B. Eremeev, A. , Horoba, C. , Neumann, F. , Theili, M. 2009. Evolutionary Algorithms and Dynamic Programming. GECCO'09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, ACM, New York, NY, USA. 771-778.
  • Lew, A. , Mauch, H. 2007. Dynamic Programming: A Computational Tool. Springer-Verlag, Berlin Heidelberg.
  • Ilaboya, I. R. , Atikpo, E. , Ekoh, G. O. , Ezugwu, M. O. , Umokoro, L. 2011. Application of Dynamic Programming to Solving Reservoir Operational Problems. Journal of Applied Technology in Environmental Sanitation, vol. 1, no. 3 (Oct. 2011). 251-262.
  • Petkov, N. 1993. Systolic Parallel Processing. Elsevier Sci. Publ. , North-Holland.
  • Carmen, T. H. , Leiserson, V. E. , Rivest, R. L. , Stein, C. 2001. Introduction to Algorithms. Second Edition, MIT.
  • Tang, P. 2008. Extending Parallel Pseudo-Code Language Peril-L. PDCCS'08: Proceedings of the 21st International Conference on Parallel and Distributed Computing and Communication Systems, New Orleans, LA, USA. 38-43, September 2008.
  • Li, G. J. , Wah, B. W. 1985. Systolic processing for dynamic programming problems. Proceddings of the International conference on parallel processing, University Park, PA, UST. 434-441, August 1985.
  • Lee, J. J. , Song, G. Y. 2002. Implementation of the systolic array for dynamic programing. Proceedings of the International conference on information technology and applications, ICITA, Bathurst, Australia. 24-28, November 2002.