Distributed algorithms for fractional coloring

DOI10.1007/978-3-030-79527-6_2OpenAlexW3173702648MaRDI QIDQ2117704FDOQ2117704

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

Publication date: 22 March 2022

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

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

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)

Cites Work

• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• The probabilistic method
• Locality in Distributed Graph Algorithms
• 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
• Distributed Graph Coloring: Fundamentals and Recent Developments
• High-girth graphs avoiding a minor are nearly bipartite
• Parallel Symmetry-Breaking in Sparse Graphs
• Finitary coloring
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• 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 \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Simple and local independent set approximation
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• A lower bound for the distributed Lovász local lemma
• LCL problems on grids
• Entropy and expansion
• An Automatic Speedup Theorem for Distributed Problems
• Brief Announcement: Classification of Distributed Binary Labeling Problems

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)