Abstract | ||
---|---|---|
We present two results on slime mold computations. In wet-lab experiments by Nakagaki et al. (2000) [1] the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slime's adaption process (Tero et al., 2007) [3]. It was shown that the process convergences to the shortest path (Bonifaci et al., 2012) [5] for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.tcs.2018.08.027 | Theoretical Computer Science |
Keywords | Field | DocType |
Physarum polycephalum,Dynamical systems,Linear programming,Optimization,Approximation algorithms | Discrete mathematics,Discretization,Combinatorics,Shortest path problem,Combinatorial optimization,Quartic function,Dynamical systems theory,Rate of convergence,Slime mold,Mathematics,Physarum polycephalum | Journal |
Volume | ISSN | Citations |
773 | 0304-3975 | 1 |
PageRank | References | Authors |
0.35 | 6 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ruben Becker | 1 | 31 | 5.27 |
Vincenzo Bonifaci | 2 | 532 | 38.78 |
Andreas Karrenbauer | 3 | 133 | 20.21 |
Pavel Kolev | 4 | 9 | 3.53 |
Kurt Mehlhorn | 5 | 5314 | 853.36 |