A Molecular Algorithm for Longest Path Problem

Abstract

The field of DNA computing has recently attracted considerable attention. Because of its great capacity to conduct parallel relations, many NP-complete problems are solved by this approach. In this paper we present a molecular algorithm to solve the Longest Path Problem. Till now, no molecular algorithm is presented for this problem in the literatures on the weighted graph G=(V, E). The proposed molecular algorithm can be performed in O(|V| 2 ) molecular operations. Special effort is spent on designing an scaling method for weight values in order to obtain an appropriate encoding for the problem. The effectiveness of this algorithm is verified by the computational simulation.