zbMATH — the first resource for mathematics

Cycle prefix digraphs for symmetric interconnection networks. (English) Zbl 0802.90043
Summary: Motivated by the study of large graphs with given degree and diameter, and the recent interest in the design of highly symmetric interconnection networks (e.g., the study of Cayley digraphs), we are led to the search for large vertex symmetric digraphs with given degree and diameter. The main result of this paper is the construction of a new class of vertex symmetric directed graphs, \(\Gamma_ \Delta(D)\) \((\Delta\geq D)\) that have degree \(\Delta\), diameter \(D\), and \((\Delta+1)\Delta\cdots (\Delta- D+2)\) vertices. The graphs \(\Gamma_ \Delta(D)\) are first found in the notation of Cayley coset digraphs. Then, we discover that they have a very simple representation in terms of sequences like the commonly studied networks such as the hypercube, de Bruijn graphs, and Kautz graphs. Based on the sequence representation, we give a simple shortest- path routing scheme. We also show that the average distance in our digraph \(\Gamma_ \Delta(D)\) is very close to its diameter \(D\). As a consequence, it follows that the natural routing scheme, which is even simpler than the shortest-path routing, is nearly optimal on an average basis.

90B18 Communication networks in operations research
Full Text: DOI
[1] Akers, IEEE Trans. Comput. 38 pp 555– (1989)
[2] On the fault-tolerance of quasi-minimal Cayley networks. Lecture Notes in Computer Science, Vol. 497. Springer-Verlag, Berlin (1991) 431–442.
[3] Discrete Appl. Math. 37/38 (1992)
[4] Bermond, J. Parallel Distributed Comput. 3 pp 433– (1986)
[5] and , The de Bruijn and Kautz networks: A competition for the hypercube. Proceedings of the First European Workshop on Hypercube and Distributed Computers, Rennes (1989) 279–293.
[6] and , The automorphism group of the cycle prefix digraph. Preprint (1992).
[7] , and , Restricted routing and wide diameter of cycle prefix networks. Preprint, Los Alamos National Laboratory (1993).
[8] and , Vertex symmetric digraphs with small diameter. Preprint (1992).
[9] and , Generators and Relations for Discrete Groups, 4th ed. Springer-Verlag, New York (1980).
[10] Algebraic methods for efficient network constructions. Master Thesis, Department of Computer Science, University of Victoria, Victoria, B. C., Canada (1991).
[11] Global communication algorithms for hypercubes and other Cayley coset graphs. Technical Report, LA-UR-87-3136, Los Alamos National Laboratory (1987).
[12] and , High-degree low-diameter interconnection networks with vertex symmetry: The directed case. Technical Report, LA-UR-88-1051, Los Alamos National Laboratory (1988).
[13] and , Interconnection networks. US Patent 5,125,076 (June 23, 1992).
[14] Parallel sorting on Cayley graphs. Preprint (1990).
[15] Hamidoune, Discrete Appl. Math. 37/38 pp 275– (1992)
[16] D. F. Hsu, Ed., Interconnection Networks and Algorithms. Special Issue Networks, to appear. · Zbl 0968.00017
[17] On container width and length in graphs, groups, and networks. Preprint (1992).
[18] and , Determining the Hamilton-connectedness of certain vertex-transitive graphs. Technical Report, DCS-202-IR, Department of Computer Science, University of Victoria, Victoria, B.C., Canada (1992).
[19] The connectivity of Cayley coset graphs. Preprint (1992).
[20] The Art of Computer Programming, Vol. 1. Addison-Wesley, Reading, MA (1973).
[21] Sabidussi, Monatsh. Math. 68 pp 426– (1969)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.