On the Solution of the Steiner Tree NP-Hard Problem via Physarum BioNetwork
Abstract
In the last several years, many algorithms trying to mimic biological processes have been proposed to enhance the performance of communication networks. However, the bio-inspired algorithms represent only the very first step toward the design of a smart adaptive communication network since: 1) they model only a limited set of the rules underlying the biological processes, thus, omitting fundamental functionalities; 2) they are executed on traditional computer architectures, thus, failing to achieve the intrinsic parallelism exhibited by biological processes. To overcome these issues, in this paper, the BioNetwork paradigm is proposed, a novel communication network paradigm in which the traditional network nodes are replaced by living organisms. The BioNetwork paradigm provides very attractive features over traditional network paradigms, such as efficiency, adaptivity, reliability, self-organization, and scalability. Moreover, it has a huge potential since it can be adopted in many different applications, such as health and military ones. In the paper, this potential is shown by proving that a BioNetwork can solve one of the most fundamental NP-hard problems in networks, i.e., the Steiner tree problem. To this aim, a BioNetwork constituted by a unicellular organism, the Physarum polycephalum slime mold, is designed. Throughout the paper, it is proven that a Physarum BioNetwork can solve the Steiner tree problem with an exponential convergence rate toward the optimal solution. The theoretical solutions are validated through a case study.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Research in biomimetic communications and underwater acoustics offers the technical crossover needed to make computational replicas of acoustic communities credible.
“Research in biomimetic communications and underwater acoustics (Caleffi et al. 2015; Casari et al. 2023) offers the technical crossover needed to make these simulations credible.”
From Listening forward: emerging roles of bioacoustics in ecology, evolution, and conservation (2026) · cites this paper as Caleffi et al. 2015
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203 · see citing works
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511 · see citing works
Reducibility Among Combinatorial Problems
Rarp, K. (2012) · Cited by 1,356 · see citing works
A fast algorithm for Steiner trees
Kou, L. T., Markowsky, G., & Berman, L. (1981) · Acta Informatica · doi:10.1007/bf00288961 · Cited by 1,199 · see citing works
Maze—solving by an amoeboid organism
Nakagaki, T., Yamada, H., & Tóth, Á. (2000) · Nature · doi:10.1038/35035159 · Cited by 1,022 · see citing works
A mathematical model for adaptive transport network in path finding by true slime mold
Tero, A., Kobayashi, R., & Nakagaki, T. (2006) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2006.07.015 · Cited by 408 · see citing works
A survey on bio-inspired networking
Dressler, F., & Akan, Ö. B. (2010) · Computer Networks · doi:10.1016/j.comnet.2009.10.024 · Cited by 316 · see citing works
Physarum solver: A biologically inspired method of road-network navigation
Tero, A., Kobayashi, R., & Nakagaki, T. (2006) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2006.01.053 · Cited by 225 · see citing works
Smart network solutions in an amoeboid organism
Nakagaki, T. (2003) · Biophysical Chemistry · doi:10.1016/s0301-4622(03)00189-3 · Cited by 160 · see citing works
SteinLib: An Updated Library on Steiner Tree Problems in Graphs
Koch, T., Martin, A. R., & Voß, S. (2001) · Combinatorial optimization · doi:10.1007/978-1-4613-0255-1_9 · Cited by 152 · see citing works
Robot control with biological cells
Tsuda, S., Zauner, K.-P., & Gunji, Y. (2006) · Biosystems · doi:10.1016/j.biosystems.2006.09.016 · Cited by 108 · see citing works
Analog computation with dynamical systems
Siegelmann, H. T., & Fishman, S. (1998) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(98)00057-8 · Cited by 68 · see citing works
Physarum Chip Project: Growing Computers From Slime Mould.
Adamatzky, A., Erokhin, V. V., Grube, M., et al. (2012) · International journal of unconventional computing · Cited by 61 · see citing works
Biological principles for future internet architecture design
Balasubramaniam, S., Leibnitz, K., Lió, P., Botvich, D., & Murata, M. (2011) · IEEE Communications Magazine · doi:10.1109/mcom.2011.5936154 · Cited by 43 · see citing works
A method inspired by Physarum for solving the Steiner problem
Tero, A., Nakagaki, T., Toyabe, K., et al. (n.d.) · Institutional Repositories DataBase (IRDB) · Cited by 34 · see citing works
Calcium Regulation of the Actin-Myosin Interaction of Physarum polycephalum
Nakamura, A., & Kohama, K. (1999) · International review of cytology · doi:10.1016/s0074-7696(08)60157-6 · Cited by 33 · see citing works
Computational Complexity for Continuous Time Dynamics
Siegelmann, H. T., Ben‐Hur, A., & Fishman, S. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.1463 · Cited by 32 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- [9][9] T. Miyaji and I. Ohnishi, 'Physarum can solve the shortest path problem on Riemannian surface mathematically rigorously,' Int. J. Pure Appl. Math. , vol. 47, no. 3, pp. 353-369, 2008. -
- [12][12] F. K. Hwang, D. S. Richards, and P. Winter , The Steiner Tree Problem , ser. Annals of Discrete Mathematics. Philadelphia, PA, USA: SIAM, 1992, vol. 53. -
Cited by
Sorted by citations
Listening forward: emerging roles of bioacoustics in ecology, evolution, and conservation
Zsebők, S. (2026) · Biologia Futura · doi:10.1007/s42977-026-00322-5
“Research in biomimetic communications and underwater acoustics (Caleffi et al. 2015; Casari et al. 2023) offers the technical crossover needed to make these simulations credible.”
- Authors
- Caleffi, M., Akyildiz, I. F., & Paura, L.
- Affiliations
- Georgia Institute of Technology (US)
- Consorzio Nazionale Interuniversitario per le Telecomunicazioni (IT)
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 2015-08
- Volume
- 23
- Issue
- 4
- Pages
- 1092-1106
- ISSN
- 1063-6692 (ISSN-L)
- 1558-2566
- OpenAlex
- W2031118896
- Cited by
- 35
- References
- 17
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 3 · 2023: 4 · 2022: 4 · 2021: 3 · 2020: 2 · 2019: 3 · 2018: 8 · 2017: 4 · 2016: 2
- FWCI
- 1.04
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE/ACM Transactions on Networking (publishedVersion)
- Funders
- University of Naples Federico II under Award Mobilita nellAmbito delle Reti di Eccellenza: POR Campania FSE 2007-2013 n Progetto MyOpenGov
- Topics
- Physical Sciences › Engineering › Biomedical Engineering › Slime Mold and Myxomycetes Research
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Keywords
- Steiner tree problem, Physarum polycephalum, slime molds, bio-inspired algorithms, NP-hard problems, convergence rate, self-organization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
