Concepedia

Removing randomness in parallel computation without a processor penalty

Journal of Computer and System Sciences · 1993 · 194 citations · 16 references

Concepts

ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismParallel Algorithm DesignParallel Complexity TheoryRandomized AlgorithmsRandomized ComputationGraph Problems In NcIndependenceIndependent Set AlgorithmsParallel Algorithm AnalysisParallel Algorithm ComplexityParallel Random Access MachineRandomized Parallel AlgorithmsRandomness-efficient Algorithms

References

16

Parallel Prefix Computation

Richard E. Ladner, Michael J. Fischer · Journal of the ACM · 1980 · 1.3K citations · Full text

Computing, Computer Science, Algorithms +10

A Simple Parallel Algorithm for the Maximal Independent Set Problem

Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations

Computing, Computer Science, Algorithms +12

CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICS

David Gottlieb, Steven A. Orszag, Peter J. Huber et al. · 2011 · 984 citations

Natural Sciences, Mathematics, Applied Mathematics +5

Parallelism in random access machines

Steven Fortune, James Wyllie · 1978 · 885 citations

Computing, Computer Science, Computer Architecture +15

A fast and simple randomized parallel algorithm for the maximal independent set problem

Noga Alon, László Babai, Alon Itai · Journal of Algorithms · 1986 · 842 citations

Computing, Computer Science, Mathematics +13