A scalable method to find the shortest path in a graph with circuits of memristors

Abstract

Finding the shortest path in a graph has applications to a wide range of optimization problems. However, algorithmic methods scale with the size of the graph in terms of time and energy. We propose a method to solve the shortest path problem using circuits of nanodevices called memristors and validate it on graphs of different sizes and topologies. It is both valid for an experimentally derived memristor model and robust to device variability. The time and energy of the computation scale with the length of the shortest path rather than with the size of the graph, making this method particularly attractive for solving large graphs with small path lengths.

References in corpus (8)

• Uncovering the overlapping community structure of complex networks in nature and society
• The diameter of the world wide web
• Memristive model of amoeba's learning
• Solving mazes with memristors: a massively-parallel approach
• Self-organization and solution of shortest-path optimization problems with memristive networks
• Slime Mould Memristors
• The complex dynamics of memristive circuits: analytical results and universal slow relaxation
• Locality of interactions for planar memristive circuits