A self-stabilizing algorithm for coloring planar graphs

DOI10.1007/BF02278856zbMath0818.68089OpenAlexW2044573924MaRDI QIDQ1310570

Sukumar Ghosh, Mehmet Hakan Karaata

Publication date: 6 January 1994

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02278856

zbMATH Keywords

directed acyclic graphdistributed algorithmself-stabilizationatomicity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (23)

SELF-STABILIZING COMPUTATION OF 3-EDGE-CONNECTED COMPONENTS ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ Argumentation through a distributed self-stabilizing approach ⋮ Self-stabilizing algorithms for minimal dominating sets and maximal independent sets ⋮ Self-stabilizing Cuts in Synchronous Networks ⋮ A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives ⋮ Local 7-coloring for planar subgraphs of unit disk graphs ⋮ An efficient self-stabilizing distance-2 coloring algorithm ⋮ A self-stabilizing algorithm for the maximum flow problem ⋮ Alternators on uniform rings of odd size ⋮ Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems ⋮ 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 ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS ⋮ A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks ⋮ A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph ⋮ Linear time self-stabilizing colorings ⋮ An Efficient Self-stabilizing Distance-2 Coloring Algorithm ⋮ Self-stabilizing coloration in anonymous planar networks ⋮ A SELF-STABILIZING ALGORITHM FOR FINDING ARTICULATION POINTS ⋮ Optimal 1-fair alternators ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs

Cites Work

• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• A belated proof of self-stabilization
• Every Planar Map is Four Colorable
• Self-stabilizing systems in spite of distributed control

This page was built for publication: A self-stabilizing algorithm for coloring planar graphs