A Massive Digital Neural Network for Total Coloring Problems

Nobuo FUNABIKI; Junji KITAMICHI; Seishi NISHIKAWA

A Massive Digital Neural Network for Total Coloring Problems

Nobuo FUNABIKI, Junji KITAMICHI, Seishi NISHIKAWA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.9 pp.1625-1629

Publication Date: 1997/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section LETTER (Special Section on Nonlinear Theory and its Applications)

Category

Cite this

Copy

Nobuo FUNABIKI, Junji KITAMICHI, Seishi NISHIKAWA, "A Massive Digital Neural Network for Total Coloring Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 9, pp. 1625-1629, September 1997, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e80-a_9_1625/_p

Copy

@ARTICLE{e80-a_9_1625,
author={Nobuo FUNABIKI, Junji KITAMICHI, Seishi NISHIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Massive Digital Neural Network for Total Coloring Problems},
year={1997},
volume={E80-A},
number={9},
pages={1625-1629},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - A Massive Digital Neural Network for Total Coloring Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1625
EP - 1629
AU - Nobuo FUNABIKI
AU - Junji KITAMICHI
AU - Seishi NISHIKAWA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1997
AB - 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.
ER -