Simple distributed \(\Delta+1\)-coloring of graphs
From MaRDI portal
Publication:1606946
DOI10.1016/S0020-0190(99)00064-2zbMath1002.68202MaRDI QIDQ1606946
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
Related Items
Unnamed Item, Unnamed Item, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS, Superfast coloring in CONGEST via efficient color sampling, Superfast coloring in CONGEST via efficient color sampling, Node and edge averaged complexities of local graph problems, Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts, A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm, 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, A framework for scalable greedy coloring on distributed-memory parallel computers, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, About randomised distributed graph colouring and graph partition algorithms, Lessons from the congested clique applied to MapReduce, Design patterns in beeping algorithms: examples, emulation, and analysis, Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge, Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains, Distributed coloring algorithms for triangle-free graphs, On the complexity of distributed graph coloring with local minimality constraints
