Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O( log² 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 Comp...") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Time Complexity == | == Time Complexity == | ||
$O( | $O(\log^{2} V)$ | ||
== Space Complexity == | == Space Complexity == | ||
Latest revision as of 08:42, 10 April 2023
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