The probabilistic method yields deterministic parallel algorithms
- 1 December 1994
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 49 (3) , 478-516
- https://doi.org/10.1016/s0022-0000(05)80069-8
Abstract
No abstract availableKeywords
This publication has 33 references indexed in Scilit:
- Simulating (log c n )-wise independence in NCJournal of the ACM, 1991
- Balanced two-colorings of finite sets in the cubeDiscrete Mathematics, 1989
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- The complexity of parallel searchJournal of Computer and System Sciences, 1988
- Efficient parallel algorithms for edge coloring problemsJournal of Algorithms, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A fast parallel algorithm for the maximal independent set problemJournal of the ACM, 1985
- Six standard deviations sufficeTransactions of the American Mathematical Society, 1985
- NP completeness of finding the chromatic index of regular graphsJournal of Algorithms, 1983
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975