On the complexity of distributed graph coloring

DOI10.1145/1146381.1146387zbMath1314.68161OpenAlexW2109368894MaRDI 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

zbMATH Keywords

graph coloringchromatic numberneighborhood graphsymmetry breakinglocalitydistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (36)

Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Exact Bounds for Distributed Graph Colouring ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Can we locally compute sparse connected subgraphs? ⋮ Large cuts with local algorithms on triangle-free graphs ⋮ 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 ⋮ What can be sampled locally? ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Computing large independent sets in a single round ⋮ Locality and checkability in wait-free computing ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ An optimal bit complexity randomized distributed MIS algorithm ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Complexity analysis of a decentralised graph colouring algorithm ⋮ Unnamed Item ⋮ About randomised distributed graph colouring and graph partition algorithms ⋮ Unnamed Item ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ 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 ⋮ 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) ⋮ Unnamed Item ⋮ Linial for lists

This page was built for publication: On the complexity of distributed graph coloring