A self-stabilizing algorithm for coloring planar graphs
Tóm tắt
This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a selfstabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one.
Tài liệu tham khảo
Appel K, Haken W. Every planar map is four-colorable. Am Math Soc 98 (1989).
Chiba N, Nishizeki T, Saito N: A linear algorithm for fivecoloring of a planar graph. Proc 17th Symp of Research Institute of Electrical Communication (1980)
Dijkstra EW: Self-stabilizing system in spite of distributed control. Commun ACM 17(11):643–644 (1974)
Dijkstra EW: A belated proof of self-stabilization. Distrib Comput 1(1):5–6 (1986)
Harary F: Graph theory. Addison-Wesley, Reading, Mass., 1969
He Xin: Eficient parallel and sequential algorithms for 4-coloring perfect planar graphs. Algorithmica 5:545–559 (1990)