Artificial Neural Networks for Four-Coloring Map Problems and K-Colorability Problems

Yoshiyasu Takefuji, Kuo Chun Lee

Research output: Contribution to journalArticlepeer-review

108 Citations (Scopus)


Coloring 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. The computational energy is presented for solving a four.

Original languageEnglish
Pages (from-to)326-333
Number of pages8
JournalIEEE transactions on circuits and systems
Issue number3
Publication statusPublished - 1991 Mar
Externally publishedYes

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Artificial Neural Networks for Four-Coloring Map Problems and K-Colorability Problems'. Together they form a unique fingerprint.

Cite this