Covering the de Bruijn Graph.
Abstract
Random-like sequences of 0's and 1's are generated efficiently by binary shift registers. The output of n-stage shift registers viewed as a sequence of binary n-tuples also give rise to a special graph called the de Bruijn graph B sub n. The de Bruijn graph is a directed graph with 2 to the nth nodes. Each node has 2 arcs entering it and 2 arcs going out of it. Thus, there are a total of 2 to the n + 1 arcs in B sub n. In this thesis, we define a cover of the de Bruijn graph, different from the usual graph theoretic cover. A cover S of the de Bruijn graph is defined as an independent subset of the nodes of B sub n that satisfy the following property. For each node x in B sub n - S, there exists a node y in S such that either the arc (x,y) or the arc (y,x) is in B sub n. Combinatorially, we are able to place both upper and lower bounds on the cardinality of S. We find examples of covers that approach these bounds in cardinality. Several algorithms are presented that produce either a maximal or a minimal cover. Among them are Frugal, Sequential Fill, Double and Redouble, Greedy and Quartering. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1986
- Accession Number
- ADA168474
Entities
People
- Roy D. Bryant
Organizations
- Naval Postgraduate School