Annals of Combinatorics 2 (1998) 165-172

Fault-tolerant Routing in Circulant Networks and Cycle Prefix networks

Sheng-Chyang Liaw1, Gerard J. Chang1, Feng Cao2, and D. Frank Hsu3

1Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
  {scliaw, gjchang}

2Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, USA

3Department of Computer and Information Science, Fordham University   LL813, 113 West 60th Street, New York, NY 10023, USA

Received October 22, 1996

AMS Subject Classification: 05C12, 05C40

Abstract. Reliability and efficiency are important criteria in the design of interconnection networks. Connectivity is a widely used measurement for network fault-tolerance capacities, while diameter determines routing efficiency along individual paths. In practice, we are interested in high-connectivity, small-diameter networks. Recently, Hsu introduced the notion of w-wide diameter, which unifies diameter and connectivity. This paper investigates the w-wide diameter dw(G) and two related parameters: w-fault diameter Dw(G) and w-Rabin number rw(G). In particular, we determine dw(G) and Dw(G) for $2 \le w \le k(G)$ and G is a circulant digraph G(dn; {1,d,...,dn-1}) or a cycle prefix digraph.

Keywords: routing, circulant network, cycle prefix network, connectivity, diameter, container, wide diameter, fault diameter, Rabin number


1.  J. C. Bermond (ed.), Interconnection Networks, Discrete Appl. Math. 37/38 (1992) special issue.

2.  W.Y.C. Chen, V. Faber, and E. Knill, Restricted routing and wide diameter of the cycle prefix network, D.F. Hsu et al., Eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 21 (1995) 31–46.

3.  D.Z. Du, D.F. Hsu, and Y.D. Lyuu, On the diameter vulnerability of Kautz digraphs, Discrete Math. 151 (1996) 81–85.

4.  D.Z. Du, Y.D. Lyuu, and D.F. Hsu, Line digraph iteration and connectivity analysis of de Bruijn and Kautz graphs, IEEE Trans. Comput. 42 (1993) 612–616.

5.  D. R. Duh and G. H. Chen, On the Rabin number problem, manuscript.

6.  A.H. Esfahanian and L. Halsimi, Fault-tolerant routing in de Bruijn communication networks, IEEE Trans. Comput. 34 (1985) 777-788.

7.  V. Faber and J.W. Moore, High-degree low-diameter interconnection networks with vertex symmetry: the directed case, Technical Report LA-UR-88-1051, Los Alamos National Laboratory, Los Alamos, New Mexico, 1988.

8.  V. Faber, J.W. Moore, and W.Y.C. Chen, Cycle prefix digraphs for symmetric interconnection networks, Networks 23 (1993) 641–649.

9.  Y.O. Hamidoune, On the connectivity of Cayley digraphs, European J. Combin. 5 (1984) 309–312.

10.  D.F. Hsu (ed.), Interconnection Networks and Algorithms, Networks, 23, John Wiley and Son, Inc., (1993) (special issue).

11.  D.F. Hsu, On container width and length in graphs, groups, and networks, IEICE Trans. Fund. Elect., Commun. Comput. Sci. E77-A (1994) 668–680.

12.  D.F. Hsu and T. Luczak, Note on the $k$-diameter of k-regular k-connected graphs, Discrete Math. 133 (1994) 291–296.

13.  D.F. Hsu and Y.D. Lyuu, A graph theoretical study of transmission delay and fault tolerance, International Journal of Mini and Microcomputers 16 (1994) 35–42.

14.  M. Imase, T. Soneoka, and K. Okada, Fault-tolerant processor interconnection networks, Systems and Computers in Japan 17 (1986) 21–30.

15.  M. Jiang and F. Ruskey, Determining the Hamilton-connectedness of certain vertex-transitive graphs, Discrete Math. 133 (1994) 159–169.

16.  M.S. Krishnamoorthy and B. Krishnamurthy, Fault diameter of interconnection networks, Comput. Math. Appl. 13 (1987) 577–582.

17.  S. Latifi, Combinatorial analysis of the fault-diameter of the n-cube, IEEE Trans. Comput. 42 (1993) 27–33.

18.  S. Latifi, On the fault-diameter of the star graph, Inform. Process. Lett. 46 (1993) 143–150.

19.  S.C. Liaw and G.J. Chang, Generalized diameters and Rabin numbers of networks, J. Combin. Optim., to appear.

20.  S.C. Liaw and G.J. Chang, Wide diameters of butterfly networks, Taiwanese J. Math., to appear.

21.  S.C. Liaw and G.J. Chang, Rabin numbers of butterfly networks, Discrete Math., to appear.

22.  F.J. Meyer and D.K. Pradhan, Flip-tree: fault-tolerant graphs with wide containers, IEEE Trans. Comput. 37 (1988) 472–478.

23.  E.T. Ordman, Fault-tolerant networks and graph connectivity, J. Combin. Math. Combin. Comput. 1 (1987) 191–205.

24.  M.O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, J. Assoc. Comput. Mach. 36 (1989) 335–348.

25.  S.M. Reddy, J.G. Kuhl, S.H. Hosslini, and H. Lee, On digraphs with minimum diameter and maximum connectivity, Proceedings of 20th Annual Allerton Conference on Communication, Control and Computing (Urbana-Champaign, Illinois, 1982), 1018–1026.

Get the LaTex | DVI | PS file of this abstract.