Title :
The replicated data algorithm for solving the single source shortest path problem
Author :
Yang, J.A. ; Zhang, D.C.
Author_Institution :
Inst. of Artificial Intelligence, Hefei Univ. of Technol., China
Abstract :
Proposes a data-parallel algorithm and a replicated data algorithm for the graph-theoretic operation of computing single-source shortest paths, and demonstrates the generality of the data replication technique by applying it to such a problem; then computes and discusses the speedup of the replicated data algorithm over the data-parallel algorithm; and, finally, points out that the data replication technique is not only applicable to fast image analysis, but is also general enough to be applicable to a large class of graph-theoretic operation problems
Keywords :
graph theory; image processing; parallel algorithms; path planning; problem solving; data-parallel algorithm; fast image analysis; generality; graph-theoretic operation; replicated data algorithm; single-source shortest path problem; speedup ratio; Artificial intelligence; Cities and towns; Concurrent computing; Costs; Ear; Graph theory; Image edge detection; Parallel algorithms; Pixel; Shortest path problem;
Conference_Titel :
Industrial Technology, 1994., Proceedings of the IEEE International Conference on
Conference_Location :
Guangzhou
Print_ISBN :
0-7803-1978-8
DOI :
10.1109/ICIT.1994.467047
