Computing fault tolerance of Cayley graphs
by Dr Shuhong Gao
Abstract: Cayley graphs from finite groups have many nice properties that make them excellent candidates for interconnection networks for computer systems. We are interested in efficient algorithms for computing fault tolerance of Cayley graphs. It is a difficult problem in general to decide whether a given Cayley graph is connected, for an instance, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. We present an algorithm for computing the fault tolerance of connected Cayley graphs. The algorithm is deterministic and has a polynomial time in terms of the vertex degree and $\log(N)$ where $N$ is the number of vertices of the given graph.
Joint work with Beth Novick.
For More Information: Lawrence Reeves email: L.Reeves@ms.unimelb.edu.au