In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to tackle a variety of computing tasks, among them the computation of shortest paths and the design of efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we generalize the dynamics to the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterizations of the optimum solution.

Bonifaci, V., Facca, E., Folz, F., Karrenbauer, A., Kolev, P., Mehlhorn, K., et al. (2022). Physarum-inspired multi-commodity flow dynamics. THEORETICAL COMPUTER SCIENCE, 920, 1-20 [10.1016/j.tcs.2022.02.001].

Physarum-inspired multi-commodity flow dynamics

Bonifaci, Vincenzo;
2022

Abstract

In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to tackle a variety of computing tasks, among them the computation of shortest paths and the design of efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we generalize the dynamics to the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterizations of the optimum solution.
Bonifaci, V., Facca, E., Folz, F., Karrenbauer, A., Kolev, P., Mehlhorn, K., et al. (2022). Physarum-inspired multi-commodity flow dynamics. THEORETICAL COMPUTER SCIENCE, 920, 1-20 [10.1016/j.tcs.2022.02.001].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/399399
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact