Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Bonifaci, Vincenzo
Mehlhorn, Kurt
Varma, Girish

dblp
dblp
dblp

Not MPG Author(s):

Varma, Girish

Editor(s):

Ravani, Yuval

dblp

Not MPII Editor(s):

Ravani, Yuval

BibTeX cite key*:

Bonifaci2012a

Title, Booktitle

Title*:

Physarum Can Compute Shortest Paths

Booktitle*:

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-12)

Event, URLs

URL of the conference:


URL for downloading the paper:

http://siam.omnibooksonline.com/2012SODA/data/papers/064.pdf

Event Address*:

Kyoto, Japan

Language:

English

Event Date*
(no longer used):


Organization:

Society for Industrial and Applied Mathematics (SIAM)

Event Start Date:

17 January 2012

Event End Date:

19 January 2012

Publisher

Name*:

SIAM

URL:

http://www.siam.org

Address*:

Philadelphia, PA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

233-240

Year*:

2012

VG Wort Pages:


ISBN/ISSN:

978-1-611972-11-5

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Physarum Polycephalum is a slime mold that is apparently able to solve shortest path problems.
A mathematical model has been proposed by biologists to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources $s_0$ and $s_1$. We prove that, under this model, the mass of the mold will eventually converge to the shortest $s_0$-$s_1$ path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution.

This matches the experimental observations by the biologists and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years.

Keywords:

Physarum, Dynamical System, Shortest Path



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Bonifaci2012a,
AUTHOR = {Bonifaci, Vincenzo and Mehlhorn, Kurt and Varma, Girish},
EDITOR = {Ravani, Yuval},
TITLE = {Physarum Can Compute Shortest Paths},
BOOKTITLE = {Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-12)},
PUBLISHER = {SIAM},
YEAR = {2012},
ORGANIZATION = {Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {233--240},
ADDRESS = {Kyoto, Japan},
ISBN = {978-1-611972-11-5},
}


Entry last modified by Anja Becker, 02/08/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/26/2012 04:21:28 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Vincenzo Bonifaci
Vincenzo Bonifaci
Vincenzo Bonifaci
Edit Dates
08.02.2013 10:42:48
11/26/2012 04:23:55 PM
11/26/2012 04:23:01 PM
11/26/2012 04:21:28 PM