Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.
Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.
复制标题
DOI：
10.1038/s41598-017-00825-1
复制
发表时间：
2017-04-19
影响因子：
4.6
通讯作者：
Raychowdhury A
中科院分区：
文献类型：
--
作者：
Parihar A;Shukla N;Jerry M;Datta S;Raychowdhury A
虽然布尔逻辑一直是数字信息处理的支柱，但存在一些计算难题，其中这种范式从根本上来说是低效的。图的顶点着色属于组合优化类别，代表了这样一个问题。它在数据科学、生命科学、社会科学和技术中的应用得到了充分的研究，因此，激发了替代的、更有效的非布尔路径来实现其解决方案。在这里，我们演示了一个基于耦合张弛振荡器的动态系统，该系统利用二氧化钒 (VO2) 中的绝缘体-金属转变来有效解决图的顶点着色问题。之前已经针对基本计算操作分析了成对耦合 VO2 振荡器电路，但使用 VO2 振荡器或任何其他振荡器的复杂网络来执行更复杂的任务在理论和实验中都具有挑战性。所提出的 VO2 振荡器网络利用高度并行、互连的动态系统中优化问题和能量最小化过程之间的自然模拟来近似最佳的图着色。我们进一步指出了线性动力系统的光谱特性和图形着色的光谱算法之间的基本联系。我们的工作不仅阐明了基于物理的计算方法，而且还为构建定制模拟协处理器以有效解决难题提供了诱人的机会。
While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO2) to efficiently solve vertex coloring of graphs. Pairwise coupled VO2 oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO2 oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO2 oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.