The partial line digraph technique in the design of large interconnection networks
- 1 July 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 41 (7) , 848-857
- https://doi.org/10.1109/12.256453
Abstract
The following problem arises in the design of some interconnection networks for distributed systems. Namely, to construct digraphs with given maximum out-degree, reduced diameter, easy routing, good connectivity, and good expandability. To this end, a method based on the concept of partial line digraph is presented. This proposal, which turns out to be a generalization of the so-called line digraph technique, allows digraphs that satisfy all the above-mentioned requirements to be obtained. In particular, it is shown that the partial line digraphs of Kautz digraphs solve the (d, N) digraph problem, i.e. to minimize the diameter D in a digraph of maximum out-degree d and number of vertices N, for any N in the range d/sup D-1/+d/sup D-2/+. . .+1or=Nor=d/sup D/+d/sup D-1/.Keywords
This publication has 13 references indexed in Scilit:
- Maximally connected digraphsJournal of Graph Theory, 1989
- Strategies for interconnection networks: Some methods from graph theoryJournal of Parallel and Distributed Computing, 1986
- Connectivity of Regular Directed Graphs with Small DiametersIEEE Transactions on Computers, 1985
- Line Digraph Iterations and the (d, k) Digraph ProblemIEEE Transactions on Computers, 1984
- A Design for Directed Graphs with Minimum DiameterIEEE Transactions on Computers, 1983
- Line digraph iterations and the (d,k) problem for directed graphsPublished by Association for Computing Machinery (ACM) ,1983
- A Survey of Interconnection NetworksComputer, 1981
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- On the impossibility of Directed Moore GraphsJournal of Combinatorial Theory, Series B, 1980
- Connectivity in digraphsPublished by Springer Nature ,1971