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:
    P093265
    Publication Type:
    Presentation
    Received Date:
    19-Mar-2018
    Last Edit Date:
    19-Mar-2018
    Research:
    2698.002 (University of Notre Dame)

Abstract

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.