Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting)

From Algorithm Wiki
Revision as of 11:15, 15 February 2023 by Admin (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 Computation

PRAM (not sure what type), SIMD computers?

Year

1981

Reference

https://www.proquest.com/docview/920003939?pq-origsite=gscholar&fromopenview=true

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Dekel;_Nassimi_%26_Sahni_Parallel_Implementation_(Topological_Sorting_Topological_Sorting)&oldid=45387"