Distributed Graph Coloring: Fundamentals and Recent Developments
From MaRDI portal
(Redirected from Publication:4980035)
arboricitycolouringdeterministic algorithmdistributed symmetry breakingmaximal independent setmaximal matchingrandomized algorithm
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Randomized algorithms (68W20)
Recommendations
- Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- The locality of distributed symmetry breaking
- Some simple distributed algorithms for sparse networks
- Distributed deterministic edge coloring using bounded neighborhood independence
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Deterministic distributed vertex coloring in polylogarithmic time
- Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
- Locally-iterative Distributed (Δ + 1)-coloring and Applications
- Exact bounds for distributed graph colouring
Cited in
(62)- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Linear-in- lower bounds in the LOCAL model
- Deterministic distributed construction of T-dominating sets in time T
- Improved distributed \(\Delta\)-coloring
- Distributed backup placement
- Local mending
- Linial for lists
- Distributed algorithms for fractional coloring
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
- Derandomizing local distributed algorithms under bandwidth restrictions
- A hierarchy of local decision
- Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains
- Distributed coloring in sparse graphs with fewer colors
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
- Deterministic subgraph detection in broadcast CONGEST
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Exact bounds for distributed graph colouring
- Simple Distributed Δ + 1 Coloring in the SINR Model
- Nearly optimal local broadcasting in the SINR model with feedback
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Locality in Distributed Graph Algorithms
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Improved dynamic graph coloring
- Price of anarchy for graph coloring games with concave payoff
- Introduction to local certification
- Distributed coloring of graphs with an optimal number of colors
- Distributed recoloring
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Equilibria of Games in Networks for Local Tasks
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Distributed arboricity-dependent graph coloring via all-to-all communication
- Network Decomposition and Distributed Derandomization (Invited Paper)
- Distributed (+1)-coloring via ultrafast graph shattering
- Distributed Coloring in Sparse Graphs with Fewer Colors
- Distributed Lower Bounds for Ruling Sets
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Distributed algorithms for the Lovász local lemma and graph coloring
- Making local algorithms wait-free: the case of ring coloring
- Node and edge averaged complexities of local graph problems
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- A note on the network coloring game: a randomized distributed (+1)-coloring algorithm
- Local conflict coloring revisited: Linial for lists
- Coloring fast without learning your neighbors' colors
- Self-stabilizing ( +1)-coloring in sublinear (in ) rounds via locally-iterative algorithms
- Borel Vizing's theorem for graphs of subexponential growth
- Secured distributed algorithms without hardness assumptions
- Fast deterministic algorithms for highly-dynamic networks
- Graph coloring via degeneracy in streaming and other space-conscious models
- The message complexity of distributed graph optimization
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Descriptive complexity for distributed computing with circuits
- Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
- Fast algorithms for Vizing's theorem on bounded degree graphs
- Locally-iterative (+1)-coloring in sublinear (in ) rounds
- Adaptive massively parallel coloring in sparse graphs
- Short and local transformations between ( +1)-colorings
- Parallel derandomization for coloring
- Title not available (Why is no real title available?)
- Optimal (degree+1)-coloring in congested clique
- Title not available (Why is no real title available?)
- Distributed algorithms for random graphs
This page was built for publication: Distributed Graph Coloring: Fundamentals and Recent Developments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4980035)
