Linear time self-stabilizing colorings

DOI10.1016/S0020-0190(03)00299-0zbMath1161.68340OpenAlexW2069413879MaRDI QIDQ1014432

Pradip K. Srimani, David P. Jacobs, Stephen T. Hedetniemi

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00299-0

zbMATH Keywords

algorithmsdistributed systemsgrundy coloringself-stabilizing coloring

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items

A self-stabilizing algorithm for the st-order problem ⋮ Self-stabilizing Cuts in Synchronous Networks ⋮ An efficient self-stabilizing distance-2 coloring algorithm ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem ⋮ 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 ⋮ Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS ⋮ A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph ⋮ An Efficient Self-stabilizing Distance-2 Coloring Algorithm ⋮ Self-stabilizing coloration in anonymous planar networks ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stabilization-preserving atomicity refinement
• A self-stabilizing algorithm for coloring planar graphs
• A self-stabilizing algorithm for coloring bipartite graphs
• On colouring random graphs
• Self-stabilizing systems in spite of distributed control
• 25 pretty graph colouring problems