Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-39212-2_42 | ICALP (2) |
Keywords | Field | DocType |
complexity bound,nonuniform case,shortest path problem,convergence proof,shortest path,mathematical model,physarum model,uniform case,physarum polycephalum,euler integration,slime mold | Convergence (routing),Discretization,Discrete mathematics,Combinatorics,Physarum,Euler method,Shortest path problem,Equilibrium point,Slime mold,Mathematics,Physarum polycephalum | Conference |
Volume | ISSN | Citations |
7966 | 0302-9743 | 10 |
PageRank | References | Authors |
0.79 | 2 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Becchetti | 1 | 945 | 55.75 |
| Vincenzo Bonifaci | 2 | 532 | 38.78 |
| Michael Dirnberger | 3 | 10 | 0.79 |
| Andreas Karrenbauer | 4 | 133 | 20.21 |
| Kurt Mehlhorn | 5 | 5314 | 853.36 |