The probabilistic method yields deterministic parallel algorithms
type: Item
instance of: scholarly article
title: The probabilistic method yields deterministic parallel algorithms
zbMATH Open document ID: 0824.68047
DOI: 10.1016/S0022-0000(05)80069-8
author: Moni Naor
author: Joseph (Seffi) Naor
author: Rajeev Motwani
published in: Journal of Computer and System Sciences
publication date: 1995-10-24T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 711694
zbMATH Keywords: RNC algorithm
zbMATH Keywords: NC algorithms
zbMATH Keywords: parallel algorithms
zbMATH Keywords: Ramsey graphs
MaRDI profile type: Publication
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
cites work: Balanced two-colorings of finite sets in the cube
cites work: ``Integer-making'' theorems
cites work: Simulating (log c n )-wise independence in NC
cites work: A deterministic view of random sampling and its use in geometry
cites work: A Randomized Algorithm for Closest-Point Queries
cites work: New applications of random sampling in computational geometry
cites work: On a combinatorial game
cites work: Q5541610
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: The NP-Completeness of Edge-Coloring
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Derandomization through approximation, an NC algorithm for minimum cuts
cites work: Efficient parallel algorithms for edge coloring problems
cites work: Constructing a perfect matching is in random NC
cites work: The complexity of parallel search
cites work: A fast parallel algorithm for the maximal independent set problem
cites work: A fast parallel algorithm for routing in permutation networks
cites work: On the ratio of optimal integral and fractional covers
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Q4146667
cites work: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
cites work: Matching is as easy as matrix inversion
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Balancing families of sets
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: Q3484356
cites work: Q3481743
cites work: Six Standard Deviations Suffice
cites work: Balancing vectors in the max norm
Recommended article: Q4251082
Recommended article: An efficient parallel algorithm for random sampling
Recommended article: Probabilistic Parallel Algorithms for Sorting and Selection
Recommended article: Q4942231
Recommended article: On Synchronous Parallel Computations with Independent Probabilistic Choice
Recommended article: Q5309370
Recommended article: An Embarrassingly Parallel Method for Large-Scale Stochastic Programs
Recommended article: Probabilistic analysis of a parallel algorithm for finding maximal independent sets
Recommended article: Correctness and determinism of parallel Monte Carlo processes
description: scientific article; zbMATH DE number 711694