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-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.
- 社団法人電子情報通信学会の論文
- 1997-09-25
著者
-
Funabiki N
Graduate School Of Natural Science And Technology Okayama University
-
Funabiki Nobuo
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
KITAMICHI Junji
the Department of Information and Computer Sciences, School of Engineering Science, Osaka University
-
NISHIKAWA Seishi
the Department of Information and Computer Sciences, School of Engineering Science, Osaka University
-
Kitamichi J
Osaka Univ. Toyonaka‐shi Jpn
-
Kitamichi Junji
The Department Of Information And Computer Sciences School Of Engineering Science Osaka University
-
Nishikawa S
The Department Of Information And Computer Sciences School Of Engineering Science Osaka University
-
Nishikawa Seishi
The Department Of Information And Computer Sciences Faculty Of Engineering Science Osaka University
関連論文
- A WDS Clustering Algorithm for Wireless Mesh Networks
- An Optical-Drop Wavelength Assignment Algorithm for Efficient Wavelength Reuse under Heterogeneous Traffic in WDM Ring Networks(Discrete Mathematics and Its Applications)
- A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks(Network)
- P2PMM_router : A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks(Discrete Mathematics and Its Applications)
- A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks(Special Section on Discrete Mathematics and Its Applications)
- A Proposal of Optimal Path Selection Algorithm for Static and Mobile Multicast Routing Problems
- Relaxation of Coefficient Sensitiveness to Performance for Neural Networks Using Neuron Filter through Total Coloring Problems
- A Proposal of Neuron Filter: A Constraint Resolution Scheme of Neural Networks for Combinatorial Optimization Problems
- A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization
- A Massive Digital Neural Network for Total Coloring Problems
- A Gradual Neural Network Approach for Time Slot Assignment in TDM Multicast Switching Systems
- Comparisons of Energy-Descent Optimization Algorithms for Maximum Clique Problems (Special Section on Discrete Mathematics and Its Applications)
- A Minimal-State Processing Search Algorithm for Graph Coloring Problems
- A Binary Neural Network Approach for Link Activation Problems in Multihop Radio Networks
- A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems(Special Section on Discrete Mathematics and Its Applications)