Title :
Solution of path problems using associative parallel processors
Author :
Nepomniaschaya, A.S.
Author_Institution :
Supercomput. Software Dept., Acad. of Sci., Novosibirsk, Russia
Abstract :
In this paper we study a question of representing a group of associative algorithms on an abstract model of the SIMD type with vertical data processing (the STAR-machine). This group includes the Warshall transitive closure algorithm, the Floyd shortest path algorithm and the Maggs-Plotkin minimal spanning tree algorithm. These algorithms are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated
Keywords :
associative processing; computational complexity; computational geometry; parallel processing; Floyd shortest path algorithm; Maggs-Plotkin minimal spanning tree algorithm; SIMD type; STAR procedures; STAR-machine; Warshall transitive closure algorithm; abstract model; associative algorithms; associative parallel processors; correctness; path problems; time complexity; vertical data processing; Arithmetic; Associative memory; Automata; Data processing; Digital audio players; Dynamic programming; Equations; Gaussian processes; Performance analysis; Supercomputers;
Conference_Titel :
Parallel and Distributed Systems, 1997. Proceedings., 1997 International Conference on
Conference_Location :
Seoul
Print_ISBN :
0-8186-8227-2
DOI :
10.1109/ICPADS.1997.652606
