A Massive Digital Neural Network for Total Coloring Problems

Nobuo FUNABIKI  Junji KITAMICHI  Seishi NISHIKAWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.9   pp.1625-1629
Publication Date: 1997/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Nonlinear Theory and its Applications)
Category: 
Keyword: 
neural network,  digital technology,  total coloring,  NP-complete,  combinatorial optimization,  

Full Text: PDF>>
Buy this Article



Summary: 
A neural network of massively interconnected digital neurons is presented for the total coloring problem in this paper. Given a graph G (V, E), the goal of this NP-complete problem is to find a color assignment on the vertices in V and the edges in E with the minimum number of colors such that no adjacent or incident pair of elements in V and E receives the same color. A graph coloring is a basic combinatorial optimization problem for a variety of practical applications. The neural network consists of (N+M) L neurons for the N-vertex-M-edge-L-color problem. Using digital neurons of binary outputs and range-limited non-negative integer inputs with a set of integer parameters, our digital neural network is greatly suitable for the implementation on digital circuits. The performance is evaluated through simulations in random graphs with the lower bounds on the number of colors. With a help of heuristic methods, the digital neural network of up to 530, 656 neurons always finds a solution in the NP-complete problem within a constant number of iteration steps on the synchronous parallel computation.