School Seminars and Colloquia

Computing fault tolerance of Cayley graphs

Geometry/Topology Seminar

by Dr Shuhong Gao


Institution: Clemson University
Date: Thu 19th July 2007
Time: 3:15 PM
Location: Old Geology Theatre 1, The University of Melbourne

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