Energy Function-Based Approaches to Graphs Coloring  

Oleh:

Jagota, A. ; Hughey, R. ; Blas, A. Di

Jenis: Article from Journal - ilmiah internasional
Dalam koleksi: IEEE Transactions on Neural Networks vol. 13 no. 1 (2002), page 81-91.
Topik: graph; energy function; approachers; graph coloring

Ketersediaan

Perpustakaan Pusat (Semanggi) Nomor Panggil: II36.6 Non-tandon: 1 (dapat dipinjam: 0) Tandon: tidak ada

Lihat Detail Induk

Isi artikel

We describe an approach to optimization based on a multiple - restart quasi - Hopfield network where the only problem - specific knowledge is embedded in the energy function that the algorithm tries to minimize. We apply this method to three different variants of the graph coloring problem : the minimum coloring problem, the spanning subgraph k - coloring problem, and the induced subgraph k - coloring problem. Though Hopfield networks have been applied in the past to the minimum coloring problem, our encoding is more natural and compact than almost all previous ones. In particular, we use k - state neurons while almost all previous approaches use binary neurons. This reduces the number of connections in the network from (Nk) 2 to N 2 asymptotically and also circumvents a problem in earlier approaches, that of multiple colors being assigned to a single vertex. Experimental results show that our approach compares favorably with other algorithms, even nonneural ones specifically developed for the graph coloring problem.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali