Calculating Parameters of De Bruijn Graphs
Abstract
Background: De Bruijn networks are a special topology of graphs that are interesting as a network model because their physical properties endow high fault-tolerance and offer a more robust communication than many other network models. Sometimes when an arbitrary node within the network is excited, it is desirable to know which other nodes are in the vicinity and through proximity may also be affected. In other words, given a node, x, find all nodes within a distance d from x. An obscure subject, there is little literature covering de Bruijn graphs outside of general characteristics and theory. In our research, we have found no published mention of an algorithm to generate all nodes within a given distance d from a node x. Results: In this paper, we present our research to design and implement a library compiled in MATLAB. This library calculates many useful de Bruijn graph parameters to include calculating directed and undirected distance between nodes, producing adjacency and minimum distance matrices, and some functions to generate lists of nodes that are within a prescribed distance from an arbitrary node. Conclusion: The resulting library works quite well. It produces the desired parameters within our targeted tolerance of efficiency.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2014
- Accession Number
- ADA616735
Entities
People
- Joel R. Moore
Organizations
- SUNY Polytechnic Institute