Title :
k-coloring vertices using a neural network with convergence to valid solutions
Author :
Berger, Matthias Oliver
Author_Institution :
Lehrstuhl fur Informatik IV, Tech. Hochschule Aachen, Germany
fDate :
27 Jun-2 Jul 1994
Abstract :
Proposes an algorithm using a maximum neural network model to k-color vertices of a simple undirected graph. Unlike traditional neural nets, the proposed network is guaranteed to converge to valid solutions with no parameter tuning needed. The power of the new method to solve this NP-complete problem is shown in a number of simulations
Keywords :
Hopfield neural nets; computational complexity; convergence; graph colouring; graph theory; optimisation; NP-complete problem; convergence; k-coloring vertices; maximum neural network model; simple undirected graph; Combinatorial mathematics; Computer networks; Cost function; Equations; Graph theory; Hopfield neural networks; Neural networks; Neurons;
Conference_Titel :
Neural Networks, 1994. IEEE World Congress on Computational Intelligence., 1994 IEEE International Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-1901-X
DOI :
10.1109/ICNN.1994.375000
