Research Article
A NonñLinear Feedback Neural Network for Graph Coloring
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 39 - Issue 16 |
| Published: February 2012 |
| Authors: Mohd. Samar Ansari, Syed Atiqur Rahman, Syed Javed Arif |
10.5120/4906-7417
|
Mohd. Samar Ansari, Syed Atiqur Rahman, Syed Javed Arif . A NonñLinear Feedback Neural Network for Graph Coloring. International Journal of Computer Applications. 39, 16 (February 2012), 31-33. DOI=10.5120/4906-7417
@article{ 10.5120/4906-7417,
author = { Mohd. Samar Ansari,Syed Atiqur Rahman,Syed Javed Arif },
title = { A NonñLinear Feedback Neural Network for Graph Coloring },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 39 },
number = { 16 },
pages = { 31-33 },
doi = { 10.5120/4906-7417 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Mohd. Samar Ansari
%A Syed Atiqur Rahman
%A Syed Javed Arif
%T A NonñLinear Feedback Neural Network for Graph Coloring%T
%J International Journal of Computer Applications
%V 39
%N 16
%P 31-33
%R 10.5120/4906-7417
%I Foundation of Computer Science (FCS), NY, USA
Abstract
A feedback neural network for solving graph coloring problem is presented. The circuit has an associated transcendental energy function that ensures fast convergence to the exact solution. Hardware and PSPICE simulation results on random and benchmark problems have been presented. Test results are compared with existing techniques for graph coloring to show that the proposed neural network model provides a significant reduction in the number of colors while enjoying a simple and efficient circuit implementation.
References
- Zeitlhofer, T. and Wess, B. 2004. A Comparison of Graph Coloring Heuristics for Register Allocation based on Coalescing in Interval Graphs. Proc. ISCAS 04, vol. IV, 529 – 532.
- El-Fishawy, N.A., Hadhood, M. M., Elnoubi, S., and El-Sersy, W.2000. A modified Hopfield neural network algorithm for cellular radio channel assignment. Proc. TENCON 2000, 2, 213 – 216.
- Blas, A.D., Jagota, A., and Hughey, R. 2002. Energy Function – Based Approaches to Graph Coloring. IEEE Trans. On Neural Networks, 13, 81–91.
- Rahman, S.A., Jayadeva and Dutta Roy, S.C. 1999. Neural network approach to graph colouring. Electronics Letters, 35(14), 1173–1175.
- Wu, C.W. 1998. Graph Coloring via Synchronization of Coupled Oscillators. IEEE Trans. Circuits Syst. I, 45(9), 974–978.
- Lui, J., Zhong, W., and Jiao, L.2006. Comments on “The 1993 DIMACS Graph Coloring Challenge” and “Energy Function-Based Approaches to Graph Coloring” IEEE Trans. On Neural Networks, 17(2), 533.
- Newcomb, R.W. and Lohn, J.D.1998. Analog VLSI for neural networks in The Handbook of Brain Theory and Neural Networks. Cambridge, MA: The MIT Press.
Index Terms
Keywords