Title :
Analysis and experiments for a parallel solution to the all pairs shortest path problem
Author :
Pramanick, Ira ; Ali, Hyder
Author_Institution :
IBM Corp., Poughkeepsie, NY, USA
fDate :
30 May-2 Jun 1994
Abstract :
This paper proposes and analyzes a parallel implementation of the matrix product algorithm for the all pairs shortest path problem for a distributed memory MIMD model. The results of experiments conducted on a 128-processor hypercube machine show that the parallel implementation achieves the performance predicted by the analysis
Keywords :
VLSI; circuit layout CAD; computational complexity; integrated circuit layout; parallel algorithms; CAD; VLSI design; all pairs shortest path problem; distributed memory MIMD model; matrix product algorithm; parallel implementation; Algorithm design and analysis; Communication networks; Computer networks; Design automation; Hypercubes; Matrices; Performance analysis; Shortest path problem; Transportation; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location :
London
Print_ISBN :
0-7803-1915-X
DOI :
10.1109/ISCAS.1994.408842
