Linear time self-stabilizing colorings

DOI10.1016/S0020-0190(03)00299-0MaRDI QIDQ1014432zbMATH OpenOpenAlexFDO

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

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 algorithms (68W15) Distributed systems (68M14)

Recommendations

• An efficient self-stabilizing distance-2 coloring algorithm
• A self-stabilizing algorithm for edge-coloring of graphs
• An efficient self-stabilizing distance-2 coloring algorithm
• SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS
• A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1919504 (Why is no real title available?)
• scientific article; zbMATH DE number 1760041 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• 25 pretty graph colouring problems
• A self-stabilizing algorithm for coloring bipartite graphs
• A self-stabilizing algorithm for coloring planar graphs
• On colouring random graphs
• Self-stabilizing systems in spite of distributed control
• Stabilization-preserving atomicity refinement

Cited in

(15)

• An efficient self-stabilizing distance-2 coloring algorithm
• A self-stabilizing algorithm for cut problems in synchronous networks
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks
• SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
• An efficient self-stabilizing distance-2 coloring algorithm
• A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph
• A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
• Self-stabilizing coloration in anonymous planar networks
• Self-stabilizing Cuts in Synchronous Networks
• A self-stabilizing algorithm for coloring bipartite graphs
• A self-stabilizing algorithm for the st-order problem
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

This page was built for publication: Linear time self-stabilizing colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014432)