License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.5
URN: urn:nbn:de:0030-drops-39166
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3916/
Go to the corresponding LIPIcs Volume Portal

Mehlhorn, Kurt

Physarum Computations (Invited talk)

pdf-format:
4.pdf (0.4 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{mehlhorn:LIPIcs:2013:3916,
  author =	{Kurt Mehlhorn},
  title =	{{Physarum Computations (Invited talk)}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{5--6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3916},
  URN =		{urn:nbn:de:0030-drops-39166},
  doi =		{10.4230/LIPIcs.STACS.2013.5},
  annote =	{Keywords: Biological computation, shortest path problems}
}

Keywords: Biological computation, shortest path problems
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI