Connecting spectral techniques for graph coloring and eigen properties of coupled dynamics: A pathway for solving combinatorial optimizations (Invited paper)

摘要

This paper reviews an analog circuit system of capacitively coupled relaxation oscillators whose time evolution can be used to solve the graph coloring problem. These oscillators consist of a series combination of an insulator-metal-transition (IMT) device and a resistance. Such circuits were also demonstrated experimentally using VO₂ (Vanadium Dioxide) as the phase transition material. The time evolution of circuit dynamics depend on eigenvectors of the adjacency matrix in the same way as is used by spectral algorithms for graph coloring. As such, a coupled network of such oscillators with piecewise linear dynamics have steady state phases which can be used to approximate the minimum vertex coloring of a graph.