Linial for lists
From MaRDI portal
Publication:2104037
DOI10.1007/S00446-022-00424-YOpenAlexW4280610780MaRDI QIDQ2104037FDOQ2104037
Authors: Yannic Maus, Tigran Tonoyan
Publication date: 9 December 2022
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-022-00424-y
Recommendations
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Deterministic distributed vertex coloring in polylogarithmic time
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
Cites Work
- Distributed Computing: A Locality-Sensitive Approach
- Locality in Distributed Graph Algorithms
- Locality based graph coloring
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
- Distributed Graph Coloring: Fundamentals and Recent Developments
- On the complexity of distributed graph coloring
- Families of finite sets in which no set is covered by the union of \(r\) others
- Title not available (Why is that?)
- Local Computation
- On the complexity of distributed graph coloring with local minimality constraints
- The Locality of Distributed Symmetry Breaking
- Some simple distributed algorithms for sparse networks
- Deterministic Distributed Vertex Coloring in Polylogarithmic Time
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Lower Bounds for Maximal Matchings and Maximal Independent Sets
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Deterministic distributed edge-coloring with fewer colors
- Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- Efficient Deterministic Distributed Coloring with Small Bandwidth
- Polynomial lower bound for distributed graph coloring in a weak LOCAL model
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
- Distributed Degree Splitting, Edge Coloring, and Orientations
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- On the complexity of local distributed graph problems
- Faster Deterministic Distributed Coloring Through Recursive List Coloring
- Locally-Iterative Distributed (Δ+ 1)
- An optimal distributed (Δ+1)-coloring algorithm?
- A lower bound for the distributed Lovász local lemma
- Locality of not-so-weak coloring
- Improved distributed degree splitting and edge coloring
- An Automatic Speedup Theorem for Distributed Problems
- Improved Distributed Delta-Coloring
- Towards the locality of Vizing’s theorem
- Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- Distributed Lower Bounds for Ruling Sets
Cited In (5)
This page was built for publication: Linial for lists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104037)