An FPGA implementation of GENET for solving graph coloring problems

Author

Lee, T.K. ; Leong, P.H.W. ; Lee, K.H. ; Chan, K.T. ; Hui, S.K. ; Yeung, H.K. ; Lo, M.F. ; Lee, J.H.M.

Author_Institution

Dept. of Comput. Sci. & Eng., Chinese Univ. of Hong Kong, Shatin, Hong Kong

fYear

1998

fDate

15-17 Apr 1998

Firstpage

284

Lastpage

285

Abstract

Constraint satisfaction problems (CSPs) can be used to model problems in a wide variety of application areas, such as time-table scheduling, bandwidth allocation, and car-sequencing. To solve a CSP means finding appropriate values for its set of variables such that all of the specified constraints are satisfied. Almost all CSPs have exponential time complexity and instances of them may require a prohibitively large amount of time to solve. Consequently, much research has been done in developing efficient methods to solve CSPs. In particular, a generic neural network (GENET) model, developed by C.J. Wang and E.P.K. Tsang (1991), has been demonstrated to work extremely well in solving many CSPs, often finding solutions where other methods fail

Keywords

constraint handling; field programmable gate arrays; graph colouring; neural net architecture; FPGA implementation; GENET; bandwidth allocation; car-sequencing; constraint satisfaction problems; generic neural network model; graph coloring problems; time complexity; time-table scheduling; Application software; Channel allocation; Computer networks; Computer science; Field programmable gate arrays; Microprogramming; Neural networks; Processor scheduling; Read-write memory; Turning;

fLanguage

English

Publisher

ieee

Conference_Titel

FPGAs for Custom Computing Machines, 1998. Proceedings. IEEE Symposium on

Conference_Location

Napa Valley, CA

Print_ISBN

0-8186-8900-5

Type

conf

DOI

10.1109/FPGA.1998.707918

Filename

707918