On the complexity of distributed graph coloring
From MaRDI portal
Publication:5177259
DOI10.1145/1146381.1146387zbMath1314.68161MaRDI QIDQ5177259
Roger Wattenhofer, Fabian Kuhn
Publication date: 10 March 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1146381.1146387
graph coloring; chromatic number; neighborhood graph; symmetry breaking; locality; distributed algorithms
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68M14: Distributed systems
68W15: Distributed algorithms
Related Items
A Time Hierarchy Theorem for the LOCAL Model, Unnamed Item, Unnamed Item, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Distributed Graph Algorithms and their Complexity: An Introduction, Unnamed Item, A distributed low tree-depth decomposition algorithm for bounded expansion classes, Weak models of distributed computing, with connections to modal logic, Distributed algorithms for the Lovász local lemma and graph coloring, Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds, 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, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, An optimal bit complexity randomized distributed MIS algorithm, About randomised distributed graph colouring and graph partition algorithms, Complexity analysis of a decentralised graph colouring algorithm, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Design patterns in beeping algorithms: examples, emulation, and analysis, Linear-in-\(\varDelta \) lower bounds in the LOCAL model, Computing large independent sets in a single round, Linial for lists, What can be sampled locally?, Combinatorial algorithms for distributed graph coloring, 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, 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), Exact Bounds for Distributed Graph Colouring
