@inproceedings{becker2012comparison,
abstract = {Recently several approaches have been presented that exploit the ability of Physarum polycephalum to connect several food sources via a network of pipes in order to maintain an efficient food distribution inside the organism. These approaches use the mechanisms found in nature in order to solve a technical problem, namely the design of constructing faulttolerant and efficient connection networks. These works comprise experiments with a real slime mold Physarum polycephalum as well as computer simulations based on a tubular model and an agent-based approach. In this work, we study the suitability of those bio-inspired approaches and compare their performance to a graph-theoretic algorithm for construction of fault-tolerant connection networks, the (k, t)-spanner algorithm. The graphtheoretic algorithm is able to construct graphs with a certain degree of fault tolerance as well as meet a given maximal path length between two arbitrary nodes. However the definition of fault tolerance in previous bio-inspired works differs to that used in graph theory. Thus in our contribution we analyze the bio-inspired approaches as well as the graph-theoretic approach for their efficiency of designing optimal fault-tolerant graphs. We demonstrate the usability of the graph-theoretic approach despite relying on a different definition of fault tolerance. We conclude that classical efficient computational algorithms from graph theory can be adapted and applied in the same field as the bio-inspired approaches for the problem of constructing efficient fault tolerant networks. They often provide an easier to use and more direct solution than bio-inspired approaches, that need more parameter tuning before getting satisfactory results.},
title = {Comparison of Bio-Inspired and Graph-Theoretic Algorithms for Design of Fault-Tolerant Networks},
author = {Becker, Matthias and Sarasureeporn, Waraphan and Szczerbicka, Helena},
booktitle = {ICAS 2012, The Eighth International Conference on Autonomic and Autonomous Systems},
year = {2012},
papertype = {fullpaper}
}