Deterministic Massively Parallel Algorithms for Ruling Sets

Shreyas Pai; Sriram V Pemmaraju

doi:10.48550/arxiv.2205.12686

Back

Deterministic Massively Parallel Algorithms for Ruling Sets

Preprint

Open access

Deterministic Massively Parallel Algorithms for Ruling Sets

Shreyas Pai and Sriram V Pemmaraju

ArXiv.org

05/25/2022

DOI: 10.48550/arxiv.2205.12686

Files and links (1)

url

https://doi.org/10.48550/arXiv.2205.12686View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

In this paper we present a deterministic $O(\log\log n)$-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with $\tilde{O}(n)$ memory; this algorithm also runs in $O(\log\log n)$ rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the $O(\log \Delta)$-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

Details

Title: Subtitle: Deterministic Massively Parallel Algorithms for Ruling Sets
Creators: Shreyas Pai
Sriram V Pemmaraju
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2205.12686
ISSN: 2331-8422
Language: English
Date posted: 05/25/2022
Academic Unit: Computer Science
Record Identifier: 9984410847502771

Metrics

1 Record Views