A NEURAL NETWORKS ALGORITHM FOR THE MINIMUM COLOURING PROBLEM USING FPGAs

Haidar Harmanani, Jean Hannouche, and Nancy Khoury

References

  1. [1] W.S. McCulloch & W.H. Pitts, A logical calculus of ideas imminent in nervous activity, Bulletin Mathematical Biophysics, 5, 1943, 115–133.
  2. [2] K. Smith, Neural networks for combinatorial optimization: A review of more than a decade of research, INFORMS Journal on Computing, 11(1), 1999, 15–34.
  3. [3] M. Garey & D. Johnson, Computers and intractability – A guide to the theory of NP-completeness (New York, NY, USA: W. H. Freeman and Company, 1979).
  4. [4] F. Leighton, A graph colouring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards, 84, 1979, 489–506.
  5. [5] D. Welsh & M. Powell, An upper bound on the chromatic number of a graph and its application to timetabling problems, Computer, 10, 1967, 85–86.
  6. [6] M. Garey, D. Johnson, & H. So, An application of graph colouring to printed circuit testing, IEEE Transactions on Circuits and Systems 23, 1976, 591–599.
  7. [7] G. Chaitin, Register allocation and Spilling via graph colouring, Proc. of the ACM SIGPLAN 82 Symposium on Compiler Construction, Boston, MA, 1982, 98–105.
  8. [8] N. Funabiki & Y. Takefuji, A neural network parallel algorithm for channel assignment problems in cellular radio networks, IEEE Transactions on Vehicular Technology, 41, 1992, 430– 437.
  9. [9] K. Smith & M. Palaniswami, Static and dynamic channel assignment using neural networks, IEEE Journal on Selected Areas in Communications, 15, 1997, 238–249.
  10. [10] D. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer System Sciences, 9, 1974, 256–278.
  11. [11] D. Johnson, C.R. Aragon, L.A. McGeoch, & C. Schevon, Optimization by simulated annealing: An experimental evaluation; Part II, Graph Colourinig and number partitioning, Operations Research, 39(3), 1991, 378–406.
  12. [12] L. Davis, Handbook of genetic algorithms (New York: Van Nostrand Reinhold, 1991).
  13. [13] M. Potkonjak & D. Kirovski, Efficient colouring of a large spectrum of graphs, Proc. of the 35th ACM/IEEE Design Automation Conference, San Francico, CA, 1998, 427–431.
  14. [14] Y. Takefuji & K.C. Lee, Artificial neural networks for fourcolouring map problems and K-colorability problems, IEEE Transactions on Circuits and Systems, 38(3), 1991, 325–333.
  15. [15] M.O. Berger, K-Colouring vertices using a neural network with convergence to valid solutions, Proc. International Conf. on Neural Networks, Nagoya, Japan, 1994, 4514–4517.
  16. [16] D.W. Gassen & J.D. Carothers, Graph colour minimization using neural networks, Proc. International Joint Conf on Neural Networks, Nagoya, Japan, 1993, 1541–1544.
  17. [17] A. Omondi & J. Rajapakse, Neural networks in FPGAs, Proc. of the 9th International Conference on Neural Information Processing (ICONIP’OZ), Orchid Country Club, Singapore, 2002.
  18. [18] A.B. Lim, J.C. Rajapakse, & A.R. Omondi, Comparative study of implementing ICNNs on FPGAs, Proc. International Joint Conference on Neural Networks, Washington, DC, USA, 2001, 177–182.
  19. [19] A. Li, Q. Wang, Z. Li, & Y. Wan, A reconfigurable approach to implement neural networks for engineering application, Proc. of the 6th World Congress on Intelligent Control and Automation, Dalian, China, 2006, 2939–2943.
  20. [20] Y. Maeda & Y. Fukuda, FPGA implementation of pulse density hopfield neural network, Proc. of International Joint Conference on Neural Networks, Orlando, Florida, USA, 2007.
  21. [21] S. Watanabe, J. Kitamichi, & K. Kuroda, A hardware algorithm for the minimum P-quasi clique cover problem, International Conference on Field Programmable Logic and Applications, Amsterdam, Netherlands, 2007, 139–144.
  22. [22] D. Abramson, K. Smith, P. Logothetis, & D. Duke, FPGA based implementation of a Hopfield neural network for solving constraint satisfaction problems, Proc. of the 24th Conference on EUROMICRO, Vaesteraas, Sweden, 1998.
  23. [23] A. Varma & Jayadeva, A novel digital neural network for the travelling salesman problem, Proc. of the 9th International Conference on Neural Information Processing, Orchid Country Club, Singapore, 2002.
  24. [24] J. Hopfield, Neurons with graded response have collective computational properties like those of two state neurons, Proceedings National Academy of Science 79, 1982, 2554–2558.
  25. [25] J. Hopfield & D.W. Tank, Neural computation of decision in optimization problems, Biological Cybernetics, 52, 1985, 141–152.
  26. [26] Y. Takefuji & K. Lee, A Near optimum parallel planarization algorithm, Science, 245, 1989, 1221–1223.
  27. [27] G. De Michelli, Synthesis and optimization of digital circuits (New York, NY, USA: McGraw-Hill, 1993).
  28. [28] D. Thomas, E. Lagnese, R. Walker, J, Nestor, R. Rajan, & R. Blackburn, Algorithmic and RT synthesis: The system architect’s workbench (Norwell, Massachusetts: Kluwer, 1990).
  29. [29] Y. Takefuji, Neural network parallel computing (Boston: Kluwer, 1992).
  30. [30] A. Hertz & D. de Werra, Using tabu search techniques for graph colouring, Computing, 39(4), 1987, 345–351.
  31. [31] M. Chams, A. Hertz, & D. de Werra, Some Experiments with simulated annealing for colouring graphs, European Journal of Operational Research, 32(2), 1987, 260–266. [a] H. Harmanani, A Neural Networks Algorithm for Data Path Synthesis, International Journal of Computers and Electrical Engineering, Elsevier Science, 29(6), June 2003, 535–551. [b] H. Harmanani, J. Hannouche, & N. Khoury, A Neural Networks Algorithm for the Minimum Coloring Problem using FPGAs, Proceedings of the IASTED International Conference on Applied Simulation and Modeling (ASM 2003), Marbella, Spain, September 2003, 152–156.

Important Links:

Go Back