Accession Number:

ADA616735

Title:

Calculating Parameters of De Bruijn Graphs

Descriptive Note:

Research paper

Corporate Author:

STATE UNIV OF NEW YORK POLYTECHNIC INST UTICA NY

Personal Author(s):

• Moore, Joel R.

Report Date:

2014-12-01

Pagination or Media Count:

35.0

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.

Descriptors:

• *GRAPHS
• ALGORITHMS
• COMMUNICATIONS NETWORKS
• MODELS
• NODES

Subject Categories:

• Operations Research
• Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE