Home // ICCGI 2012, The Seventh International Multi-Conference on Computing in the Global Information Technology // View article

Solving Shortest Hamiltonion Path Problem Using DNA Computing

Authors:
Hala Alshamlan
Mohammed Menai

Keywords: Shortest Path Problem; Hamilinion Shortest Path Problem; DNA Computing; NP Hard Problems

Abstract:
Deoxyribonucleic acid (DNA) computing fundamentally being similar to parallel computing provides a nice way to make trillions of similar calculations in less than moment. Moreover, DNA computing has ability to solve main NP-complete problems such as Hamilton Path Problem, 3-SAT Problem, and Maximum Clique Problem. In this paper, we apply DNA computing to solve Shortest Hamiltonian Path Problem using two steps. First one, determine all Hamiltonian path from specific weighted graph, and then, in second step, we select the shortest one and return it as solution of our problem.

Pages: 76 to 82

Copyright: Copyright (c) IARIA, 2012

Publication date: June 24, 2012

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-202-8

Location: Venice, Italy

Dates: from June 24, 2012 to June 29, 2012