Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

Abstract 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....

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Abhinav Parihar, Nikhil Shukla, Matthew Jerry, Suman Datta, Arijit Raychowdhury
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/0399ad6e9bfc4366bea4e13fbf62a389
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:0399ad6e9bfc4366bea4e13fbf62a389
record_format	dspace
spelling	oai:doaj.org-article:0399ad6e9bfc4366bea4e13fbf62a3892021-12-02T16:07:00ZVertex coloring of graphs via phase dynamics of coupled oscillatory networks10.1038/s41598-017-00825-12045-2322https://doaj.org/article/0399ad6e9bfc4366bea4e13fbf62a3892017-04-01T00:00:00Zhttps://doi.org/10.1038/s41598-017-00825-1https://doaj.org/toc/2045-2322Abstract 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.Abhinav PariharNikhil ShuklaMatthew JerrySuman DattaArijit RaychowdhuryNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 7, Iss 1, Pp 1-11 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Abhinav Parihar Nikhil Shukla Matthew Jerry Suman Datta Arijit Raychowdhury Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
description	Abstract 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.
format	article
author	Abhinav Parihar Nikhil Shukla Matthew Jerry Suman Datta Arijit Raychowdhury
author_facet	Abhinav Parihar Nikhil Shukla Matthew Jerry Suman Datta Arijit Raychowdhury
author_sort	Abhinav Parihar
title	Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
title_short	Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
title_full	Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
title_fullStr	Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
title_full_unstemmed	Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
title_sort	vertex coloring of graphs via phase dynamics of coupled oscillatory networks
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/0399ad6e9bfc4366bea4e13fbf62a389
work_keys_str_mv	AT abhinavparihar vertexcoloringofgraphsviaphasedynamicsofcoupledoscillatorynetworks AT nikhilshukla vertexcoloringofgraphsviaphasedynamicsofcoupledoscillatorynetworks AT matthewjerry vertexcoloringofgraphsviaphasedynamicsofcoupledoscillatorynetworks AT sumandatta vertexcoloringofgraphsviaphasedynamicsofcoupledoscillatorynetworks AT arijitraychowdhury vertexcoloringofgraphsviaphasedynamicsofcoupledoscillatorynetworks
_version_	1718384758328655872

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

Ejemplares similares