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