On the complexity of distributed graph coloring
From MaRDI portal
Recommendations
Cited in
(56)- Simple distributed +1-coloring of graphs
- Vertex coloring with communication and local memory constraints in synchronous broadcast networks
- Design patterns in beeping algorithms: examples, emulation, and analysis
- Polynomial lower bound for distributed graph coloring in a weak LOCAL model
- Linear-in- lower bounds in the LOCAL model
- Computing large independent sets in a single round
- Linial for lists
- Distributed algorithms for fractional coloring
- What can be sampled locally?
- Combinatorial algorithms for distributed graph coloring
- Distributed balanced color assignment on arbitrary networks
- Distributed computing with advice: information sensitivity of graph coloring
- Can we locally compute sparse connected subgraphs?
- Large cuts with local algorithms on triangle-free graphs
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- Locality and checkability in wait-free computing
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- scientific article; zbMATH DE number 1696533 (Why is no real title available?)
- On lower bounds for the time and the bit complexity of some probabilistic distributed graph algorithms. Extended abstract
- On the complexity of distributed graph coloring with local minimality constraints
- Trading bit, message, and time complexity of distributed algorithms
- Combinatorial algorithms for distributed graph coloring
- Locality and checkability in wait-free computing
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Exact bounds for distributed graph colouring
- On the Complexity of Distributed Greedy Coloring
- On the time and the bit complexity of distributed randomised anonymous ring colouring
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Locality in Distributed Graph Algorithms
- scientific article; zbMATH DE number 6850477 (Why is no real title available?)
- A time hierarchy theorem for the LOCAL model
- Streaming and massively parallel algorithms for edge coloring
- The role of a-priori information in networks of rational agents
- Distributed recoloring
- Distributed (+1)-coloring via ultrafast graph shattering
- Distributed graph algorithms and their complexity: an introduction
- Hardness of Minimal Symmetry Breaking in Distributed Computing
- Deterministic distributed vertex coloring in polylogarithmic time
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Distributed Coloring in Sparse Graphs with Fewer Colors
- Space-efficient local computation algorithms
- Weak models of distributed computing, with connections to modal logic
- Distributed algorithms for the Lovász local lemma and graph coloring
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Local conflict coloring revisited: Linial for lists
- Coloring fast without learning your neighbors' colors
- An optimal bit complexity randomized distributed MIS algorithm
- Locally-iterative (+1)-coloring in sublinear (in ) rounds
- About randomised distributed graph colouring and graph partition algorithms
- Title not available (Why is no real title available?)
- Complexity analysis of a decentralised graph colouring algorithm
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
This page was built for publication: On the complexity of distributed graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177259)
