Artificial neural networks for four-coloring map problems and K-colorability problems
Yoshiyasu Takefuji, K.C. Lee · IEEE Transactions on Circuits and Systems · 1991
The computational energy required for solving a four-coloring map problem is determined. A parallel algorithm for solving the problem based on the McCulloch-Pits binary neuron model and the Hopfield neural network, is presented. It is shown that the computational energy is always guaranteed to monotonically decrease with the Newton equation. A 4*n neural array is used to color a map of n regions, where each neuron is a processing element that performs according to the proposed Newton equation. The capability of this system is demonstrated for a large number of simulation runs. The parallel algorithm is extended for solving the K-colorability problem.>