A DNA Algorithm for Calculating the Maximum Flow of a Network

[1] Adleman, L., Molecular computation of solutions to combinatorial problems, Science 266, 1021–1024 (1994).Search in Google Scholar

[2] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Upper Saddle River, NJ, 1993.Search in Google Scholar

[3] Benenson, Y., DNA computes a square root, Nature Nanotechnology 6, 465–467 (2011).Search in Google Scholar

[4] Błażewicz, J., Formanowicz, P., Urbaniak, R., DNA Based Algorithms for Some Scheduling Problems, In: Raidl, G. et al. Applications of Evolutionary Computing. EvoWorkshops 2003. LNCS 2611, Springer, Berlin, Heidelberg, 673–683 (2003).Search in Google Scholar

[5] Braich, R. S., Chelyapov, N., Johnson, C., Rothemund, P. W. K., and Adleman, L., Solution of a 20-variable 3-SAT problem on a DNA compute, Science 296, 499–502 (2002).Search in Google Scholar

[6] Condon, A., Designed DNA molecules: principles and applications of molecular nanotechnology, Nat. Rev. Genet. 7, 565–575 (2006).Search in Google Scholar

[7] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms (2nd edition). MIT Press, Cambridge/MA, 2001.Search in Google Scholar

[8] Darehmiraki M., A New Solution for Maximal Clique Problem based Sticker Model, BioSystems 95, 145–149 (2009).Search in Google Scholar

[9] Dodge, M., S. A. MirHassani, S. A., Hooshmand, F., Solving two-dimensional cutting stock problem via a DNA computing algorithm, Natural Computing 20, 145–159 (2021).Search in Google Scholar

[10] Eghdami, H., Darehmiraki, M., Application of DNA computing in graph theory, Artificial Intelligence Review 38, 223–235 (2012).Search in Google Scholar

[11] Elias, P., Feinstein, A., and Shannon, C. E., A note on the maximum flow through a network, IEEE Trans. Info. Theory. 2, 117–119 (1956).Search in Google Scholar

[12] Faulhammer, D., Cukras, A. R., Lipton, R. J., and Landweber, L. F., Molecular computation: RNA solutions to chess problems, Proc. of Natl. Acad. Sci. USA 97, 1385–1389 (2000).Search in Google Scholar

[13] Ford, L. R., Jr. and Fulkerson, D. R., Maximal flow through a network, Canad. J. Mathem. 8, 399–404 (1956).Search in Google Scholar

[14] Han, A. and Zhu, D., DNA encoding method of weight for Chinese postman problem, In Proc. of IEEE Congress on Evolutionary Computation, IEEE Press, pp. 681–686 (2006).Search in Google Scholar

[15] Ibrahim, Z., Towards solving weighted graph problems by direct-proportional length-based DNA computing, Research Report, IEEE Computational Intelligence Society (CIS) Walter J. Karplus Summer Research Grant (2004).Search in Google Scholar

[16] Jeng, D. J.-F., Kim, I., and Watada, J., Bio-soft computing with fixed-length DNA to a group control optimization problem, Soft Computing 12, 223–228 (2008).Search in Google Scholar

[17] Jungnickel, D., Graphs, Networks and Algorithms, Vol. 5 (2nd edition), Springer, Berlin (2005).Search in Google Scholar

[18] Lee, J. Y., Shin, S. Y., Augh, S. J., Park, T. H., and T., Z. B., Temperature gradient-based DNA computing for graph problems with weighted edges, In DNA8: 8th Intern Workshop on DNA Based Computers, LNCS 2568, Springer, London, pp. 73–84 (2003).Search in Google Scholar

[19] Lipton, R. J., DNA solution of hard computational problems, Science 268, 524–548 (1995).Search in Google Scholar

[20] Liu, Q., Wang, L., Frutos, A. G., Condon, A. E., Corn, R. M., and Smith, L. M., DNA computing on surfaces, Nature 403, 175–179 (2000).Search in Google Scholar

[21] Liu, Y., Xu, J., Pan, L., and Wang, S., DNA solution of a graph coloring problem, J. Chem. Inf. Comput. Sci. 42, 524–528 (2002).Search in Google Scholar

[22] Martínez-Pérez, I. M., Gong, Z., Ignatova, Z., and Zimmermann, K. H., Solving the maximum clique problem via DNA hairpin formation, Technical Report 06.3, Computer Engerneering Department TUHH, Germany (2006).Search in Google Scholar

[23] Nagy, N. and Akl, S. G., Aspects of biomolecular computing, Parallel. Proc. Lett. 17, 185–211 (2007).Search in Google Scholar

[24] Narayanan, A. and Zorbalas, S., DNA algorithms for computing shortest paths In Proc. of Genetic Programming, 718–723 (1998).Search in Google Scholar

[25] Ouyang, Q., Kaplan, P. D., Liu, S., and Libchaber, A., DNA solution of the maximal clique problem, Science 278, 446–449 (1997).Search in Google Scholar

[26] Păun, G., Rozenberg, G., and Salomaa, A., DNA Computing: new computing paradigms. Springer, Berlin (1998).Search in Google Scholar

[27] Ran, T., Kaplan, S., Shapiro, E., Molecular implementation of simple logic programs, Nature Nanotechnology 4, 642–648 (2009).Search in Google Scholar

[28] Razzazi, M. and Roayaei, M., Using sticker model of DNA computing to solve domatic partition, kernel and induced path problems, Information Sciences 181, 3581–3600 (2011).Search in Google Scholar

[29] Ren, X., Wang, X., Wang, Z., Wu, T., Parallel DNA Algorithms of Generalized Traveling Salesman Problem-Based Bioinspired Computing Model, International Journal of Computational Intelligence Systems 14, 228–237 (2021).Search in Google Scholar

[30] Roweis, S., Winfree, E., Burgoyne, R., Chelyapov, N. V., Goodman, M. F., Rothemund, P. W. K., Adleman, L. M., A sticker-based model for DNA computation, Journal of Computational Biology 5, 615–629 (1998).Search in Google Scholar

[31] Sager, J. and Stefanovic, D., Designing nucleotide sequences for computation: A survey of constraints, In DNA11: 11th Intern Workshop on DNA Based Computers, LNCS 3892, Springer, London, pp. 275–289 (2006).Search in Google Scholar

[32] Sakamoto, K., Gouzu, H., Komiya, K., Kiga, D., Yokoyama, S., Yokomori, T., and Hagiya, M., Molecular computation by DNA hairpin formation, Science 288, 1223–1226 (2000).Search in Google Scholar

[33] Stojanovic, M. N. and Stefanovic, D., A deoxyribozyme-based molecular automaton, Nat. Biotechnol. 21, 1069–1074 (2003).Search in Google Scholar

[34] Tian, X., Liu, X., Zhang, H., Sun, M., Zhao, Y., A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model, PLOS ONE 15, e0242083 (2020).Search in Google Scholar

[35] Woods, D., Doty, D., Myhrvold, C., Hui, J., Zhou, F., Yin, P., Winfree, E., Diverse and robust molecular algorithms using reprogrammable DNA self-assembly, Nature 567, 366-372 (2019).Search in Google Scholar

[36] Xu, J., Qiang, X., Zhang, K., Zhang, C., Yang, J., A DNA computing model for the graph vertex coloring problem based on a probe graph, Engineering 4, 61–77 (2018).Search in Google Scholar

[37] Yamamoto, M., Matsuura, N., Shiba, T., Kawazoe, Y., and Ohuchi, A., Solutions of shortest path problems by concentration control, In DNA7: 7th Intern Workshop on DNA Based Computers, LNCS 2340, Springer, London, 203–212 (2002).Search in Google Scholar

[38] Yang, J., Yin, Z., Tang, Z., Huang, K., Cui, J., Yang, X., Search computing model for the knapsack problem based on DNA origami, Materials Express 9, 553–562 (2019).Search in Google Scholar

[39] Zimmermann, K.-H., Efficient DNA sticker algorithms for NP-complete graph problems, newblock Computer Physics Communications 144, 297–309 (2002).Search in Google Scholar