Comparison of Bio-Inspired and Graph-Theoretic Algorithms for Design of Fault-Tolerant Networks

Content Provider	Semantic Scholar
Author	Becker, Matthias Sarasureeporn, Waraphan Szczerbicka, Helena
Copyright Year	2012
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.
Starting Page	1
Ending Page	7
Page Count	7
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www.thinkmind.org/download.php?articleid=icas_2012_1_10_20067
Journal	ICAS 2012
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article