Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime's behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + ε)-approximation of the shortest path in O(mL (logn + logL)/ε3) iterations, with arithmetic on numbers of O(log(nL/ε)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case. © 2013 Springer-Verlag.
Physarum can compute shortest paths: Convergence proofs and complexity bounds / Becchetti, Luca; Vincenzo, Bonifaci; Michael, Dirnberger; Andreas, Karrenbauer; Kurt, Mehlhorn. - STAMPA. - 7966:PART 2(2013), pp. 472-483. (Intervento presentato al convegno 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 tenutosi a Riga nel 8 July 2013 through 12 July 2013) [10.1007/978-3-642-39212-2_42].
Physarum can compute shortest paths: Convergence proofs and complexity bounds
BECCHETTI, Luca;
2013
Abstract
Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime's behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + ε)-approximation of the shortest path in O(mL (logn + logL)/ε3) iterations, with arithmetic on numbers of O(log(nL/ε)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case. © 2013 Springer-Verlag.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2013_11573-651998.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
577.96 kB
Formato
Adobe PDF
|
577.96 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
