Fault-tolerant networks based on the de Bruijn graph
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (10) , 1167-1174
- https://doi.org/10.1109/12.93750
Abstract
The authors introduce a novel class of networks based on the de Bruijn graph. These directed graphs are regular of degree, have N=k/sup n/ vertices for some n, and can tolerate up to k-2 node faults. Their fault-free diameter is n=log/sub k/N, and this is increases by at most 1 hop in the presence of k-2 faults. This class is very rich: for any given N=k/sup n/, one can construct at least 2/sup N/ different graphs. This is in sharp contrast to most other such constructions (including the de Bruijn graph), in which only one graph exists for each N. It is also shown how to implement certain algorithms on these networks.Keywords
This publication has 18 references indexed in Scilit:
- Fault-Tolerant Routing in DeBruijn Comrnunication NetworksIEEE Transactions on Computers, 1985
- Connectivity of Regular Directed Graphs with Small DiametersIEEE Transactions on Computers, 1985
- Efficient String Matching with Don’t-Care PatternsPublished by Springer Nature ,1985
- Fault-Tolerant Multiprocessor Link and Bus Network ArchitecturesIEEE Transactions on Computers, 1985
- A Fault-Tolerant Communication Architecture for Distributed SystemsIEEE Transactions on Computers, 1982
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Directed graphs with unique paths of fixed lengthJournal of Combinatorial Theory, Series B, 1978
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift RegistersIEEE Transactions on Computers, 1970