Solution of path problems using associative parallel processors
Anna Nepomniaschaya · 2002
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.