P. polycephalum Can Compute Shortest Paths

Luca Becchetti; Vincenco Bonifaci; Michael Dirnberger; Andreas Karrenbauer; Kurt Mehlhorn; Girish Varma

The First International Workshop on Physarum Transport Networks

Research Article

P. polycephalum Can Compute Shortest Paths

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/eai.3-12-2015.2262470,
    author={Luca Becchetti and Vincenco Bonifaci and Michael Dirnberger and Andreas Karrenbauer and Kurt Mehlhorn and Girish Varma},
    title={P. polycephalum Can Compute Shortest Paths},
    proceedings={The First International Workshop on Physarum Transport Networks},
    publisher={ACM},
    proceedings_a={PHYSNET},
    year={2016},
    month={5},
    keywords={p polycephalum graph algorithms shortest path},
    doi={10.4108/eai.3-12-2015.2262470}
}

Luca Becchetti
Vincenco Bonifaci
Michael Dirnberger
Andreas Karrenbauer
Kurt Mehlhorn
Girish Varma
Year: 2016
P. polycephalum Can Compute Shortest Paths
PHYSNET
ACM
DOI: 10.4108/eai.3-12-2015.2262470

Luca Becchetti¹, Vincenco Bonifaci², Michael Dirnberger³^,*, Andreas Karrenbauer³, Kurt Mehlhorn³, Girish Varma⁴

1: Sapienza Università di Roma
2: Istituto di Analisi dei Sistemi ed Informatica
3: Max Planck Institute for Informatics
4: Tata Institute of Fundamental Research

*Contact email: mtd@mpi-inf.mpg.de

Abstract

We demonstrate that a simple model of P. polycephalum can be used to compute shortest paths between two points in a graph. Reminiscent of how the real organism behaves in a maze when presented with two distinct food sources s and t, the algorithm gradually identifies the shortest s-t path by retreating from everywhere else in the graph.

Keywords: p polycephalum graph algorithms shortest path

Published: 2016-05-24
Publisher: ACM

: http://dx.doi.org/10.4108/eai.3-12-2015.2262470