A Fast Derandomization Scheme and Its Applications

DOI10.1137/S0097539790192702zbMath0847.05088OpenAlexW1976313192MaRDI QIDQ4875445

Yijie Han

Publication date: 5 June 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539790192702

zbMATH Keywords

parallel algorithmsgraph algorithmstime complexitymaximal matchingmaximal independent setvertex-coloringfast derandomization scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (5)

Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ Improved algorithms via approximations of probability distributions ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC ⋮ An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs

This page was built for publication: A Fast Derandomization Scheme and Its Applications