The week's pick
Random Articles
Reseach Article
Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| 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, Sabreen M. Shukr . Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming. International Journal of Computer Applications. 54, 1 ( September 2012), 21-26. DOI=10.5120/8531-2063
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.
Index Terms
Keywords