<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>DNA computing is a highly interdisciplinary field which combines molecular operations with theoretical algorithm design. A number of algorithms have been demonstrated in DNA computing, but to date network flow problems have not been studied. We aim to provide an approach to calculate the value of the maximum flow in networks by encoding the mathematical problem in DNA molecules and by using molecular biology techniques to manipulate the DNA. We present results which demonstrate that the algorithm works for an example network problem.</p>
<p>This paper presents the first application of DNA computing to network-flow problems. The presented algorithm has a linear time complexity where the calculation itself is done in a constant number of steps.</p>
</abstract>

DNA computing is a highly interdisciplinary field which combines molecular operations with theoretical algorithm design. A number of algorithms have been demonstrated in DNA computing, but to date network flow problems have not been studied. We aim to provide an approach to calculate the value of the maximum flow in networks by encoding the mathematical problem in DNA molecules and by using molecular biology techniques to manipulate the DNA. We present results which demonstrate that the algorithm works for an example network problem.
This paper presents the first application of DNA computing to network-flow problems. The presented algorithm has a linear time complexity where the calculation itself is done in a constant number of steps.

A DNA Algorithm for Calculating the Maximum Flow of a Network

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"A DNA Algorithm for Calculating the Maximum Flow of a Network"}

DNA computing is a highly interdisciplinary field which combines molecular operations with theoretical algorithm design. A number of algorithms have been...

A DNA Algorithm for Calculating the Maximum Flow of a Network

Online veröffentlicht: 21. Dez. 2023

Seitenbereich: 483 - 506

Eingereicht: 12. Apr. 2022

Akzeptiert: 05. Dez. 2023

DOI: https://doi.org/10.2478/fcds-2023-0021

Schlüsselwörter
DNA computing, Network problems, Max-flow, Min-cut

© 2023 Andrea Sackmann et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

A DNA Algorithm for Calculating the Maximum Flow of a Network

Online veröffentlicht: 21. Dez. 2023

Seitenbereich: 483 - 506

Eingereicht: 12. Apr. 2022

Akzeptiert: 05. Dez. 2023

DOI: https://doi.org/10.2478/fcds-2023-0021

SchlüsselwörterDNA computing, Network problems, Max-flow, Min-cut

© 2023 Andrea Sackmann et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Schlüsselwörter
DNA computing, Network problems, Max-flow, Min-cut