Fault-tolerant routings in chordal ring networks

This paper studies routing vulnerability in networks modeled by chordal rin g graphs. In a chordal ring graph, the vortices are labeled in Z(2n) and ea ch even vertex i is adjacent to the vertices i + a, i + b, i + c, where a, b, and c are different odd integers. Our study is based on a geometrical re presentation that associates to the graph a tile which periodically tessell ates the plane. Using this approach, we present some previous results on tr iple-loop graphs, including an algorithm to calculate the coordinates of a given vertex in the tile. Then, an optimal consistent fault-tolerant routin g of shortest paths is defined for a chordal ring graph with odd diameter a nd maximum order. This is accomplished by associating to the chordal ring g raph a triple-loop one. When some faulty elements are present in the networ k, we give a method to obtain central vertices, which are vertices that can be used to reroute any communication affected by the faulty elements. This implies that the diameter of the corresponding surviving route graph is op timum. (C) 2000 John Wiley & Sons, Inc.