Using read-k inequalities to analyze a distributed MIS algorithm

DOI10.4230/LIPICS.OPODIS.2016.9MaRDI QIDQ3174932zbMATH OpenOpenAlexFDO

Authors Talal Riaz, Sriram Pemmaraju

Publication date 18 July 2018

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

zbMATH Keywords

bounded arboricity graphsCONGEST modelLuby's algorithmmaximal independent setread-\(k\) inequality

Mathematics Subject Classification ID

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

Recommendations

• Brief announcement: Using read-k inequalities to analyze a distributed MIS algorithm
• An Improved Distributed Algorithm for Maximal Independent Set
• MIS on trees
• An optimal bit complexity randomized distributed MIS algorithm
• Distributed Maximal Independent Set using Small Messages

Cited in

(1)

• Brief announcement: Using read-k inequalities to analyze a distributed MIS algorithm

This page was built for publication: Using read-\(k\) inequalities to analyze a distributed MIS algorithm

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