Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs
Open Access
- 13 June 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 88-98
Abstract
No abstract availableAll Related Versions
Funding Information
- Austrian Science Fund (I6915, P36280)
This publication has 25 references indexed in Scilit:
- Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS2024
- Distributed Lower Bounds for Ruling Sets2020
- Derandomizing local distributed algorithms under bandwidth restrictionsDistributed Computing, 2020
- Deterministic Distributed Ruling Sets of Line Graphs2018
- Symmetry breaking depending on the chromatic number or the neighborhood growthTheoretical Computer Science, 2013
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decompositionDistributed Computing, 2009
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- Parallel tree contraction and its application1985