ARTIFICIAL NEURAL NETWORKS FOR 4-COLORING MAP PROBLEMS AND K-COLORABILITY PROBLEMS

The computational energy is presented for solving a fourcoloring map problem. The map-coloring problem is defined that one wants to color the regions of a map in such a way that no two adjacent regions (that is, regions sharing some common boundary) are of the same color. This paper presents a parallel algorithm based on the McCulloch-Pitts binary neuron model and the Hopfield neural network. It is shown that the computational energy is always guaranteed to monotonically decrease with the Newton equation. A 4 x n neural array is used to color a map of n regions where each neuron as a processing element performs the proposed Newton equation. The capability of our system is demonstrated through a large number of simulation runs. The parallel algorithm is extended for solving the K-colorability problem.