Removing randomness in parallel computation without a processor penalty

DOI10.1016/0022-0000(93)90033-SzbMath0784.68035OpenAlexW2118288908MaRDI QIDQ1309384

Michael Luby

Publication date: 20 December 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90033-s

zbMATH Keywords

pairwise independencevertex coloringrandomized parallel algorithmsmaximal matchingCREW PRAMmaximal independentdeterministic parallel algorithmsvertex indexing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Related Items (18)

Neighborhood graphs and distributed Δ+1-coloring ⋮ The local nature of \(\Delta\)-coloring and its algorithmic applications ⋮ A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity ⋮ Unnamed Item ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Deterministic Massively Parallel Connectivity ⋮ Node and edge averaged complexities of local graph problems ⋮ Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ An improvement on parallel computation of a maximal matching ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Improved algorithms via approximations of probability distributions ⋮ Improved Dynamic Graph Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• An improved parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Merge Sort
• Parallel Prefix Computation
• Simulating (log ^c n )-wise independence in NC
• Parallelism in random access machines

This page was built for publication: Removing randomness in parallel computation without a processor penalty