Faster deterministic distributed MIS and approximate matching
From MaRDI portal
Publication:6499340
DOI10.1145/3564246.3585243WikidataQ130838886 ScholiaQ130838886MaRDI QIDQ6499340
Christoph Grunau, Mohsen Ghaffari
Publication date: 8 May 2024
Cites Work
- Fast distributed network decompositions and covers
- Removing randomness in parallel computation without a processor penalty
- Low diameter graph decompositions
- Improved deterministic distributed matching via rounding
- Derandomizing local distributed algorithms under bandwidth restrictions
- On the Distributed Complexity of Computing Maximal Matchings
- On the Locality of Some NP-Complete Problems
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Complexity of network synchronization
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- On the complexity of local distributed graph problems
- Lower Bounds for Maximal Matchings and Maximal Independent Sets
- Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- An optimal distributed (Δ+1)-coloring algorithm?
- Fast randomized algorithms for distributed edge coloring
- Distributed Strong Diameter Network Decomposition
- Efficient Deterministic Distributed Coloring with Small Bandwidth
This page was built for publication: Faster deterministic distributed MIS and approximate matching
