Time-work tradeoffs for parallel algorithms.

Time-work tradeoffs for parallel algorithms.

Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort,...

Cur síos iomlán

Sonraí bibleagrafaíochta
Foilsithe in:Journal of the ACM 44, 5 (1997).
Príomhchruthaitheoir: Spencer, Thomas H.
Formáid: Alt
Teanga:English
Ábhair:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Computations on discrete structures.
Computation by abstract devices.
Modes of computation.
Parallelism and concurrency.
Mathematics of computing.
Discrete mathematics.
Graph theory.
Graph algorithms.
Algorithms.
Performance.
Theory.