JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]


Journal of Information Science and Engineering, Vol. 26 No. 1, pp. 163-181


A Fault-Containing Self-Stabilizing Algorithm for 6-Coloring Planar Graphs


JI-CHERNG LIN AND MING-YI CHIU
Department of Computer Science and Engineering 
Yuan Ze University 
Chungli, 320 Taiwan


    This paper presents the first fault-containing self-stabilizing algorithm which can 6- color any planar graph. Besides the capability to contain the fault in any single-fault situation, the proposed algorithm also has the capability to stabilize faster in single-fault situations. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), whereas the worst-case stabilization times of all the previous self-stabilizing algorithms for 6-coloring planar graphs are Ω(n), where Δ is the maximum node degree, and n is the number of nodes in the system.


Keywords: self-stabilization, fault-containment, stabilization time, graph coloring, planar graph

  Retrieve PDF document (JISE_201001_12.pdf)