A 2-dimensional optical architecture for solving Hamiltonian path problem based on micro ring resonators

作者：Shakeri Nadim; Jalili Saeed^*; Ahmadi Vahid; Zali Aref Rasoulzadeh; Goliaei Sama

来源：Optics and Laser Technology, 2015, 65: 56-65.

DOI：10.1016/j.optlastec.2014.06.008

• Optical computing
• Optoelectronic devices
• NP-complete problems

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

• 出版日期2015-1