Derandomized concentration bounds for polynomials, and hypergraph maximal independent set

zbMATH Open1403.68334MaRDI QIDQ4608035FDOQ4608035

Authors: David G. Harris 

Publication date: 15 March 2018

Full work available at URL: http://dl.acm.org/citation.cfm?id=3175446

Recommendations

• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
• Tight Analysis of Parallel Randomized Greedy MIS
• Tight analysis of parallel randomized greedy MIS

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Parallel algorithms in computer science (68W10)

Cited In (2)

• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

This page was built for publication: Derandomized concentration bounds for polynomials, and hypergraph maximal independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608035)