Randomized self-stabilization under distributed daemon for 6-coloring planar graph

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang, Cheng Feng Yeh

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


Self-stabilization is a fault-tolerant mechanism that enables a distributed system to recover from transient faults. In this paper, we consider the coloring problem and propose the first self-stabilizing algorithm under the distributed daemon model to 6-color planar graphs. The algorithm is randomized, anonymous and uniform. Starting from any initial configuration, it finds a proper coloring in O(n) rounds for an n-node graph.

Original languageEnglish
Title of host publicationAdvances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan
EditorsJain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung
Number of pages8
StatePublished - 2013

Publication series

NameSmart Innovation, Systems and Technologies
ISSN (Print)2190-3018
ISSN (Electronic)2190-3026


  • Distributed computing
  • Graph coloring
  • Planar graph
  • Randomization
  • Selfstabilization


Dive into the research topics of 'Randomized self-stabilization under distributed daemon for 6-coloring planar graph'. Together they form a unique fingerprint.

Cite this