Derandomized concentration bounds for polynomials, and hypergraph maximal independent set

MaRDI QIDQ4608035zbMATH OpenFDO

Authors David G. Harris

Publication date 15 March 2018

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

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)

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

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)