2 papers
cs.DS2026
A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We revisit the complexity analysis of the recursive version of the randomized greedy algorithm for computing a maximal independent set (MIS), originally analyzed by Yoshida, Yamamo…
cs.DS2019
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak +1
We introduce a set of techniques that allow for efficiently generating many independent random walks in the Massive Parallel Computation (MPC) model with space per machine strongly…