کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
732218 | 1461633 | 2015 | 10 صفحه PDF | دانلود رایگان |
• 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 (n2).
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(n2).
Journal: Optics & Laser Technology - Volume 65, January 2015, Pages 56–65