Computer Science/Discrete Mathematics Seminar I

In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze. Subsequently, the workings of Physarum were mathematically modeled as a dynamical system and algorithms inspired by this model were proposed to solve several graph problems. If these algorithms could be shown to work, it would raise the tantalizing possibility that nature, via evolution, has developed algorithms that could efficiently solve some of the most complex graph problems. An important step towards this was taken by Becchetti et al. who proved that one such algorithm for the shortest path problem on undirected graphs is efficient. In this talk I will show that Physarum-based algorithms can also efficiently solve flow problems on undirected and directed graphs. This is joint work with Damian Straszak.