Distributed Lower Bounds for Ruling Sets (Q5863326)

scientific article; zbMATH DE number 7488096

Language	Label	Description	Also known as
English	Distributed Lower Bounds for Ruling Sets	scientific article; zbMATH DE number 7488096

Statements

instance of

scholarly article

0 references

title

Distributed Lower Bounds for Ruling Sets (English)

0 references

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

11 March 2022

0 references

full work available at URL

https://arxiv.org/abs/2004.08282

0 references

zbMATH Keywords

distributed computing

0 references

LOCAL model

0 references

lower bounds

0 references

maximal independent set

0 references

ruling set

0 references

round elimination

0 references

describes a project that uses

GitHub

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Brief Announcement: Classification of Distributed Binary Labeling Problems

0 references

Hardness of Minimal Symmetry Breaking in Distributed Computing

0 references

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

0 references

Deterministic Distributed Vertex Coloring in Polylogarithmic Time

0 references

Distributed Graph Coloring: Fundamentals and Recent Developments

0 references

Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time

0 references

The Locality of Distributed Symmetry Breaking

0 references

An Automatic Speedup Theorem for Distributed Problems

0 references

A lower bound for the distributed Lovász local lemma

0 references

Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants

0 references

An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model

0 references

An optimal distributed (Δ+1)-coloring algorithm?

0 references

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma

0 references

Distributed algorithms for the Lovász local lemma and graph coloring

0 references

Regular graphs of large girth and arbitrary degree

0 references

A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs

0 references

An Improved Distributed Algorithm for Maximal Independent Set

0 references

Distributed Maximal Independent Set using Small Messages

0 references

Polylogarithmic-time deterministic network decomposition and distributed derandomization

0 references

Improved Distributed Delta-Coloring

0 references

Linear-in-delta lower bounds in the LOCAL model

0 references

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

0 references

A fast parallel algorithm for the maximal independent set problem

0 references

Super-Fast 3-Ruling Sets.

0 references

Deterministic distributed ruling sets of line graphs

0 references

Local Computation

0 references

MIS on trees

0 references

Locality in Distributed Graph Algorithms

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

0 references

What Can be Computed Locally?

0 references

Brief Announcement: Round eliminator: a tool for automatic speedup simulation

0 references

Brief Announcement

0 references

On the Complexity of Distributed Network Decomposition

0 references

Distributed Computing: A Locality-Sensitive Approach

0 references

Symmetry breaking depending on the chromatic number or the neighborhood growth

0 references

A new technique for distributed symmetry breaking

0 references

An optimal maximal independent set algorithm for bounded-independence graphs

0 references

Identifiers

DOI

10.1137/20M1381770

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5863326