Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

DOI10.4230/LIPICS.OPODIS.2016.9zbMath1432.68560OpenAlexW2962997742MaRDI QIDQ3174932

Talal Riaz, Sriram V. Pemmaraju

Publication date: 18 July 2018

Full work available at URL: http://dblp.uni-trier.de/db/journals/corr/corr1605.html#PemmarajuR16

zbMATH Keywords

maximal independent setCONGEST modelbounded arboricity graphsLuby's algorithmread-\(k\) inequality

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15)

This page was built for publication: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm