Previous [ 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 (January 2010)

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(£G), whereas the worst-case stabilization times of all the previous self-stabilizing algorithms for 6-coloring planar graphs are £[(n), where £G 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

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201001_12.pdf)

Received January 31, 2008; revised September 1, 2008 & January 5, 2009; accepted April 9, 2009.
Communicated by Nancy M. Amato.