2026-07-23T03:28:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3916 2024-03-06T10:34:37Z ddc:004 open_access

Physarum Computations (Invited Talk) Mehlhorn, Kurt Biological computation shortest path problems Physarum is a slime mold. It was observed over the past 10 years that the mold is able to solve shortest path problems and to construct good Steiner networks [9, 11, 8].In a nutshell, the shortest path experiment is as follows: A maze is covered with mold and food is then provided at two positions s and t and the evolution of the slime is observed. Over time, the slime retracts to the shortest s-t-path. A video showing the wet-lab experiment can be found at http://www.youtube.com/watch?v=tLO2n3YMcXw&t=4m43s. We strongly recommend to watch this video. A mathematical model of the slime's dynamic behavior was proposed in 2007 [10]. Extensive computer simulations of the mathematical model confirm the wet-lab findings. For the edges on the shortest path, the diameter converges to one, and for the edges off the shortest path, the diameter converges to zero. We review the wet-lab and the computer experiments and provide a proof for these experimental findings. The proof was developed over a sequence of papers [6, 7, 4, 2, 1, 3]. We recommend the last two papers for first reading. An interesting connection between Physarum and ant computations is made in [5]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kurt Mehlhorn 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.5 urn:nbn:de:0030-drops-39166 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.5 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode