Graph Coloring via Locally-Active Memristor Oscillatory Networks

Publikation: Beitrag in FachzeitschriftForschungsartikelEingeladenBegutachtung



This manuscript provides a comprehensive tutorial on the operating principles of a bio-inspired Cellular Nonlinear Network, leveraging the local activity of NbO x memristors to apply a spike-based computing paradigm, which is expected to deliver such a separation between the steady-state phases of its capacitively-coupled oscillators, relative to a reference cell, as to unveal the classification of the nodes of the associated graphs into the least number of groups, according to the rules of a non-deterministic polynomial-hard combinatorial optimization problem, known as vertex coloring. Besides providing the theoretical foundations of the bio-inspired signal-processing paradigm, implemented by the proposed Memristor Oscillatory Network, and presenting pedagogical examples, illustrating how the phase dynamics of the memristive computing engine enables to solve the graph coloring problem, the paper further presents strategies to compensate for an imbalance in the number of couplings per oscillator, to counteract the intrinsic variability observed in the electrical behaviours of memristor samples from the same batch, and to prevent the impasse appearing when the array attains a steady-state corresponding to a local minimum of the optimization goal. The proposed Memristor Cellular Nonlinear Network, endowed with ad hoc circuitry for the implementation of these control strategies, is found to classify the vertices of a wide set of graphs in a number of color groups lower than the cardinality of the set of colors identified by traditional either software or hardware competitor systems. Given that, under nominal operating conditions, a biological system, such as the brain, is naturally capable to optimise energy consumption in problem-solving activities, the capability of locally-active memristor nanotechnologies to enable the circuit implementation of bio-inspired signal processing paradigms is expected to pave the way toward electronics with higher time and energy efficiency than state-of-the-art purely-CMOS hardware.


Seiten (von - bis)1-30
FachzeitschriftJournal of Low Power Electronics and Applications
PublikationsstatusVeröffentlicht - 18 Apr. 2022

Externe IDs

Scopus 85129106337
WOS 000816101700001
Mendeley 0aff1e4e-3549-3eb2-b33b-f8b0477533c3
unpaywall 10.3390/jlpea12020022
ORCID /0000-0001-7436-0103/work/142240350
ORCID /0000-0003-1830-0370/work/142241789


Ziele für nachhaltige Entwicklung

ASJC Scopus Sachgebiete


  • cellular nonlinear networks, control theory, graph coloring, locally-active memristors, memristor oscillatory networks