Covering the de Bruijn graph
Authors
Bryant, Roy Dale
Subjects
Cover
de Bruijn Cycle
de Bruijn Graph
Feedback Function
Matching
Shift Register
de Bruijn Cycle
de Bruijn Graph
Feedback Function
Matching
Shift Register
Advisors
Fredricksen, Harold
Date of Issue
1986-03
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Random-like sequences of 0's and l'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 . The de Bruijn graph is a directed graph with 2n nodes. Each node has 2 arcs entering it and 2 arcs going out of it. Thus, there are a total of 2n+1 arcs in Bn. 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 Bn that satisfy the following J property. For each node x in Bn - S, there exists a node y in S such that either the arc or the arc is in Bn. 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.
Type
Thesis
Description
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
102 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.