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 im-minent in nervous activity, Bulletin Mathematical Biophysics,5, 1943, 115–133.
  2. [2] K. Smith, Neural networks for combinatorial optimization: Areview of more than a decade of research, INFORMS Journalon Computing, 11(1), 1999, 15–34.
  3. [3] M. Garey & D. Johnson, Computers and intractability – Aguide 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 schedulingproblems, Journal of Research of the National Bureau ofStandards, 84, 1979, 489–506.
  5. [5] D. Welsh & M. Powell, An upper bound on the chromaticnumber 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 graphcolouring to printed circuit testing, IEEE Transactions onCircuits 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 CompilerConstruction, Boston, MA, 1982, 98–105.
  8. [8] N. Funabiki & Y. Takefuji, A neural network parallel algorithmfor 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 channelassignment using neural networks, IEEE Journal on SelectedAreas in Communications, 15, 1997, 238–249.
  10. [10] D. Johnson, Approximation algorithms for combinatorial prob-lems, Journal of Computer System Sciences, 9, 1974, 256–278.
  11. [11] D. Johnson, C.R. Aragon, L.A. McGeoch, & C. Schevon, Opti-mization by simulated annealing: An experimental evaluation;Part II, Graph Colourinig and number partitioning, OperationsResearch, 39(3), 1991, 378–406.
  12. [12] L. Davis, Handbook of genetic algorithms (New York: VanNostrand Reinhold, 1991).
  13. [13] M. Potkonjak & D. Kirovski, Efficient colouring of a largespectrum of graphs, Proc. of the 35th ACM/IEEE DesignAutomation Conference, San Francico, CA, 1998, 427–431.
  14. [14] Y. Takefuji & K.C. Lee, Artificial neural networks for four-colouring map problems and K-colorability problems, IEEETransactions on Circuits and Systems, 38(3), 1991, 325–333.
  15. [15] M.O. Berger, K-Colouring vertices using a neural network withconvergence to valid solutions, Proc. International Conf. onNeural Networks, Nagoya, Japan, 1994, 4514–4517.
  16. [16] D.W. Gassen & J.D. Carothers, Graph colour minimizationusing neural networks, Proc. International Joint Conf onNeural Networks, Nagoya, Japan, 1993, 1541–1544.
  17. [17] A. Omondi & J. Rajapakse, Neural networks in FPGAs, Proc.of the 9th International Conference on Neural InformationProcessing (ICONIP’OZ), Orchid Country Club, Singapore,2002.
  18. [18] A.B. Lim, J.C. Rajapakse, & A.R. Omondi, Comparative studyof implementing ICNNs on FPGAs, Proc. International JointConference on Neural Networks, Washington, DC, USA, 2001,177–182.
  19. [19] A. Li, Q. Wang, Z. Li, & Y. Wan, A reconfigurable approach toimplement neural networks for engineering application, Proc. ofthe 6th World Congress on Intelligent Control and Automation,Dalian, China, 2006, 2939–2943.
  20. [20] Y. Maeda & Y. Fukuda, FPGA implementation of pulsedensity hopfield neural network, Proc. of International JointConference on Neural Networks, Orlando, Florida, USA, 2007.
  21. [21] S. Watanabe, J. Kitamichi, & K. Kuroda, A hardware algorithmfor the minimum P-quasi clique cover problem, InternationalConference on Field Programmable Logic and Applications,Amsterdam, Netherlands, 2007, 139–144.
  22. [22] D. Abramson, K. Smith, P. Logothetis, & D. Duke, FPGAbased implementation of a Hopfield neural network for solvingconstraint satisfaction problems, Proc. of the 24th Conferenceon EUROMICRO, Vaesteraas, Sweden, 1998.
  23. [23] A. Varma & Jayadeva, A novel digital neural network for thetravelling salesman problem, Proc. of the 9th InternationalConference on Neural Information Processing, Orchid CountryClub, Singapore, 2002.
  24. [24] J. Hopfield, Neurons with graded response have collectivecomputational 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 decisionin optimization problems, Biological Cybernetics, 52, 1985,141–152.
  26. [26] Y. Takefuji & K. Lee, A Near optimum parallel planarizationalgorithm, 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 systemarchitect’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 forgraph colouring, Computing, 39(4), 1987, 345–351.
  31. [31] M. Chams, A. Hertz, & D. de Werra, Some Experiments withsimulated annealing for colouring graphs, European Journal ofOperational Research, 32(2), 1987, 260–266.[a] H. Harmanani, A Neural Networks Algorithm for Data PathSynthesis, International Journal of Computers and ElectricalEngineering, Elsevier Science, 29(6), June 2003, 535–551.[b] H. Harmanani, J. Hannouche, & N. Khoury, A Neural Net-works Algorithm for the Minimum Coloring Problem usingFPGAs, Proceedings of the IASTED International Conferenceon Applied Simulation and Modeling (ASM 2003), Marbella,Spain, September 2003, 152–156.

Important Links:

Go Back