CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

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

by Nuha A. S. Alwan, Ibraheem K. Ibraheem, Sabreen M. Shukr
journal cover thumbnail

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

@article{ 10.5120/8531-2063,
author = { Nuha A. S. Alwan, Ibraheem K. Ibraheem, Sabreen M. Shukr },
title = { Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming },
journal = { International Journal of Computer Applications },
issue_date = { September 2012 },
volume = { 54 },
number = { 1 },
month = { September },
year = { 2012 },
issn = { 0975-8887 },
pages = { 21-26 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume54/number1/8531-2063/ },
doi = { 10.5120/8531-2063 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:56:06.913074+05:30
%A Nuha A. S. Alwan
%A Ibraheem K. Ibraheem
%A Sabreen M. Shukr
%T Fast Computation of the Shortest Path Problem through Simultaneous Forward and Backward Systolic Dynamic Programming
%J International Journal of Computer Applications
%@ 0975-8887
%V 54
%N 1
%P 21-26
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Sedgewick, R. , Wayne, K. 2011. Algorithms. Fourth edition, Addison-Wesley, Upper Saddle River, NJ.
  2. Stallings, W. 2011. Data and Computer Communications. Ninth edition, Pearson.
  3. Glisic, S. , Lorenzo, B. 2009. Advanced Wireless Networks. Second edition, Wiley.
  4. 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.
  5. Dasgupta, S. , Papadimitriou, C. , Vazirani, U. 2007. Algorithms. McGraw-Hill.
  6. 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.
  7. Elmallah, E. S. , Culberson, J. 1995. Multicommodity Flows in Simple Multistage Networks. Networks, vol. 25. 19-30.
  8. Moon, T. K. , Stirling, W. C. 2000. Mathematical Methods and Algorithms for Signal Processing. Upper Saddle River, New Jersey: Prentice-Hall.
  9. 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.
  10. Lew, A. , Mauch, H. 2007. Dynamic Programming: A Computational Tool. Springer-Verlag, Berlin Heidelberg.
  11. 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.
  12. Petkov, N. 1993. Systolic Parallel Processing. Elsevier Sci. Publ. , North-Holland.
  13. Carmen, T. H. , Leiserson, V. E. , Rivest, R. L. , Stein, C. 2001. Introduction to Algorithms. Second Edition, MIT.
  14. 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.
  15. 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.
  16. 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

Computer Science
Information Sciences

Keywords

Systolic array directed acyclic graph dynamic programming least cost latency throughput

Powered by PhDFocusTM