Distributed Lower Bounds for Ruling Sets

DOI10.1137/20M1381770MaRDI QIDQ5863326zbMATH OpenOpenAlexFDO

Authors Alkida Balliu, Sebastian F. Brandt, Dennis Olivetti

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

distributed computinglower boundsmaximal independent setLOCAL modelruling setround elimination

Mathematics Subject Classification ID

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

Recommendations

• Deterministic distributed ruling sets of line graphs
• Super-fast 3-ruling sets
• Distributed ∆-coloring plays hide-and-seek
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Lower Bounds for Maximal Matchings and Maximal Independent Sets

Cites work

• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• 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 for the distributed Lovász local lemma
• A new technique for distributed symmetry breaking
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• An Automatic Speedup Theorem for Distributed Problems
• An Improved Distributed Algorithm for Maximal Independent Set
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• An optimal distributed (+1)-coloring algorithm?
• An optimal maximal independent set algorithm for bounded-independence graphs
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
• Deterministic distributed ruling sets of line graphs
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed Maximal Independent Set using Small Messages
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• Improved distributed delta-coloring
• Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
• Linear-in- lower bounds in the LOCAL model
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• MIS on trees
• On the Complexity of Distributed Network Decomposition
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Regular graphs of large girth and arbitrary degree
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Super-fast 3-ruling sets
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• The locality of distributed symmetry breaking
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• What Can be Computed Locally?

Cited in

(6)

• Linial for lists
• Brief announcement: Massively parallel ruling set made deterministic
• Tight lower bounds in the supported LOCAL model
• Locally computing edge orientations
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Distributed symmetry breaking on power graphs via sparsification

Describes a project that uses

Uses Software

• GitHub

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

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