Scalable Method to Find the Shortest Path in a Graph with Circuits of Memristors

Area of Science:

• Computational Science
• Materials Science
• Electrical Engineering

Background:

• Shortest path algorithms are crucial for optimization but computationally intensive.
• Existing algorithmic methods face scalability challenges with increasing graph size, demanding significant time and energy.
• Memristor-based computing offers a potential alternative for tackling complex graph problems.

Purpose of the Study:

• To develop and validate a novel method for solving the shortest path problem using memristor circuits.
• To assess the performance and scalability of this memristor-based approach on graphs of varying sizes and topologies.
• To demonstrate the robustness of the proposed method against device variability in memristor models.

Main Methods:

• Utilized circuits composed of memristors, a type of nanodevice, to implement shortest path computations.
• Validated the proposed method on a diverse set of graphs, examining different sizes and topological structures.
• Employed an experimentally derived memristor model to ensure practical relevance and tested for robustness against device variability.

Main Results:

• The memristor-based method successfully solves the shortest path problem across various graph configurations.
• The computational time and energy requirements scale with the length of the shortest path, not the overall graph size.
• The approach demonstrated validity with a realistic memristor model and resilience to variations in device characteristics.

Conclusions:

• Memristor circuits offer a promising, energy-efficient alternative for shortest path computations, particularly for large graphs.
• The proposed method's unique scaling properties make it highly attractive for optimization problems where path length is a key factor.
• This memristor-based solution provides a robust and scalable pathway towards next-generation graph processing.