Distributed algorithms for fractional coloring

DOI10.1007/978-3-030-79527-6_2MaRDI QIDQ2117704zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, L. Esperet, François Pirot

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2012.01752

zbMATH Keywords

distributed algorithmsgraph coloringfractional coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Recommendations

• Distributed algorithms for coloring interval graphs
• Combinatorial algorithms for distributed graph coloring
• Combinatorial algorithms for distributed graph coloring
• On the Complexity of Distributed Greedy Coloring
• On the complexity of distributed graph coloring
• Distributed coloring algorithms for triangle-free graphs
• Distributed graph coloring in a few rounds
• Distributed coloring of graphs with an optimal number of colors
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Efficient randomized distributed coloring in CONGEST

Cites work

• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• A lower bound for the distributed Lovász local lemma
• A time hierarchy theorem for the LOCAL model
• An Automatic Speedup Theorem for Distributed Problems
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Entropy and expansion
• Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable
• Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs
• Finitary coloring
• Fractional colorings with large denominators
• High-girth graphs avoiding a minor are nearly bipartite
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Kneser's conjecture, chromatic number, and homotopy
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• Parallel Symmetry-Breaking in Sparse Graphs
• Simple and local independent set approximation
• The probabilistic method

Cited in

(2)

• Distributed coloring and the local structure of unit-disk graphs
• Distributed algorithms for fractional coloring

This page was built for publication: Distributed algorithms for fractional coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117704)