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.
Becchetti, L., Bonifaci, V., Dirnberger, M., Karrenbauer, A., Mehlhorn, K. (2013). Physarum can compute shortest paths: Convergence proofs and complexity bounds. In Proc. 40th Int. Colloquium on Automata, Languages and Programming (pp.472-483). Berlin : Springer [10.1007/978-3-642-39212-2_42].
Physarum can compute shortest paths: Convergence proofs and complexity bounds
Bonifaci V.;
2013-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
