A massive digital neural network for total coloring problems

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-compIete 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-edgeL-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-compIete problem within a constant number of iteration steps on the synchronous parallel computation.