[13a-C42-1~8] 9.3 Nanoelectronics

△ [13a-C42-7] Solving Planar Graph Coloring Problem Using Natural Computing Architecture

〇Masayuki Shiomura¹, Takanari Saito¹, Yusuke Kihara¹, Jun-ichi Shirakashi¹ (1.Tokyo Univ. Agr. & Tech.)

Keywords:Combinatorial Optimization Problem, Planar Graph Coloring Problem, Logic Circuit

組合せ最適化問題を解く手法として、自然現象の収束動作を利用したナチュラルコンピューティングが注目されている。これまで我々は、論理演算によるイジングスピンモデルの実装と、揺らぎを含んだ新しいスピン判定論理の提案を行い、実際に組合せ最適化問題の検討を行ってきた。今回は、この判定論理を応用したスピン配列計算機をエミュレートし、グラフ彩色問題への適用を検討した。