Distributed algorithms for fractional coloring
From MaRDI portal
Publication:2117704
DOI10.1007/978-3-030-79527-6_2OpenAlexW3173702648MaRDI QIDQ2117704
François Pirot, Louis Esperet, Nicolas Bousquet
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2012.01752
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Kneser's conjecture, chromatic number, and homotopy
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Finitary coloring
- High-girth graphs avoiding a minor are nearly bipartite
- Entropy and expansion
- Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable
- Invariant Gaussian processes and independent sets on regular graphs of large girth
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- A Time Hierarchy Theorem for the LOCAL Model
- Fractional colorings with large denominators
- Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs
- Distributed Graph Coloring: Fundamentals and Recent Developments
- An Automatic Speedup Theorem for Distributed Problems
- A lower bound for the distributed Lovász local lemma
- LCL Problems on Grids
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- Simple and local independent set approximation
