A 2-dimensional optical architecture for solving Hamiltonian path problem based on micro ring resonators. (January 2015)

• Record Type: Journal Article
• Authors: Shakeri, Nadim; Jalili, Saeed; Ahmadi, Vahid; Rasoulzadeh Zali, Aref; Goliaei, Sama
• Is Part Of: Optics & laser technology. Volume 65(2015)
• Page Start: 56
• Page End: 65
• Publication Date: 2015-01
• Subjects: Optical computing -- Optoelectronic devices -- NP-complete problems; Optics -- Periodicals; Lasers -- Periodicals; Electronic journals; 621.366
• DOI: 10.1016/j.optlastec.2014.06.008
• Languages: English
• ISSNs: 0030-3992

Abstract

Abstract: The problem of finding the Hamiltonian path in a graph, or deciding whether a graph has a Hamiltonian path or not, is an NP-complete problem. No exact solution has been found yet, to solve this problem using polynomial amount of time and space. In this paper, we propose a two dimensional (2-D) optical architecture based on optical electronic devices such as micro ring resonators, optical circulators and MEMS based mirror (MEMS-M) to solve the Hamiltonian Path Problem, for undirected graphs in linear time. It uses a heuristic algorithm and employs n +1 different wavelengths of a light ray, to check whether a Hamiltonian path exists or not on a graph with n vertices. Then if a Hamiltonian path exists, it reports the path. The device complexity of the proposed architecture is O( n 2 ). Highlights: We propose a two dimensional (2-D) optical architecture. The architecture solves a Hamiltonian path problem on undirected graph. We solve a Hamiltonian path problem in linear time. We use optoelectronic devices as Micro Ring Resonator, MEMS-mirror and circulator. The complexity of our architecture is O ( n 2 ).