Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting)
Jump to navigation
Jump to search
Time Complexity
$O(\log^{2} V)$
Space Complexity
$O(V^{2})$?? words
(Their n*n*n cube setup seems to only require each processor to keep track of one entry A(i, j), B(i, j) and propagates the results across the structure, only requiring O(1) auxiliary space per processor. Comparison sorting can be done easily with O(1) auxiliary space per processor.)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
PRAM (not sure what type), SIMD computers?
Year
1981
Reference
https://www.proquest.com/docview/920003939?pq-origsite=gscholar&fromopenview=true