A study on lower bound of direct proportional length-based DNA computing for shortest path problem

• Main Authors: Ibrahim, Zuwairie, Tsuboi, Yusei, Ono, Osamu, Khalid, Marzuki
• Other Authors: Zhang, J.
• Format: Book Section
• Published: Springer 2005
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://eprints.utm.my/id/eprint/7164/; https://link.springer.com/chapter/10.1007/978-3-540-30497-5_12; http://dx.doi.org/10.1007/b104566

Previously, we proposed a direct proportional length-based DNA computing approach for weighted graph problem. The approach has been proposed essentially to overcome the shortcoming of constant proportional length-based DNA computing approach. However, by using this approach, the minimum weight of edges that can be encoded is limited. Hence, in this paper, the lower bound, in term of minimum weight that can be encoded by direct proportional length-based DNA computing is analyzed. Also, the parameters contribute to the lower bound are investigated in order to identify the relation between those parameters and the lower bound of the direct proportional length-based DNA computing approach.