Connecting Spectral Techniques for Graph Coloring and Eigen Properties of Coupled Dynamics: A Pathway for Solving Combinatorial Optimizations

  • Authors:
    Abhinav Parihar (Georgia Tech), Nikhil Shukla (Univ. of Notre Dame), Matthew J. Jerry (Univ. of Notre Dame), Suman Datta (Univ. of Notre Dame), Arijit Raychowdhury (Georgia Tech)
    Publication ID:
    Publication Type:
    Received Date:
    Last Edit Date:
    2698.002 (University of Notre Dame)


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 VO2 (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.

4819 Emperor Blvd, Suite 300 Durham, NC 27703 Voice: (919) 941-9400 Fax: (919) 941-9450

Important Information for the SRC website. This site uses cookies to store information on your computer. By continuing to use our site, you consent to our cookies. If you are not happy with the use of these cookies, please review our Cookie Policy to learn how they can be disabled. By disabling cookies, some features of the site will not work.