An Efficient Adaptive Routing Algorithm for the Faulty Star Graph

摘要

This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n - 1 and is n - 1 -connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault- free star graph is presented. For a given destination in the n-star graph, n - 1 node-disjoint and edge-disjoint subgraphs, which are derived from n - 1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search.