Distributed Lower Bounds for Ruling Sets

DOI10.1137/20M1381770OpenAlexW4210854863MaRDI QIDQ5863326

Alkida Balliu, Dennis Olivetti, Sebastian F. Brandt

Publication date: 11 March 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.08282

zbMATH Keywords

lower boundsdistributed computingmaximal independent setLOCAL modelruling setround elimination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (2)

Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Linial for lists

Uses Software

• GitHub

Cites Work

• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Regular graphs of large girth and arbitrary degree
• An optimal maximal independent set algorithm for bounded-independence graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Deterministic distributed ruling sets of line graphs
• MIS on trees
• Linear-in-delta lower bounds in the LOCAL model
• Super-Fast 3-Ruling Sets.
• Local Computation
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• What Can be Computed Locally?
• On the Complexity of Distributed Network Decomposition
• Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• An Automatic Speedup Theorem for Distributed Problems
• A new technique for distributed symmetry breaking
• Improved Distributed Delta-Coloring
• An optimal distributed (Δ+1)-coloring algorithm?
• Distributed Maximal Independent Set using Small Messages
• A lower bound for the distributed Lovász local lemma
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Brief Announcement
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation
• Distributed algorithms for the Lovász local lemma and graph coloring

This page was built for publication: Distributed Lower Bounds for Ruling Sets