File:Double Eulerian cycles on de Bruijn digraphs (IA doubleeulericycl1094542901).pdf
Original file (1,275 × 1,650 pixels, file size: 4.95 MB, MIME type: application/pdf, 147 pages)
Captions
Summary
[edit]Double Eulerian cycles on de Bruijn digraphs ( ) | ||
---|---|---|
Author |
Krahn, Gary William |
|
Title |
Double Eulerian cycles on de Bruijn digraphs |
|
Publisher |
Monterey, California. Naval Postgraduate School |
|
Description |
A binary de Bruijn sequence has the property that every n-tuple is distinct on a given period of length 2". An efficient algorithm to generate a class of classi- cal de Bruijn sequences is given based upon the distance between cycles within the Good - de Bruijn digraph. The de Bruijn property on binary sequences is shown to be a randomness property of the ZERO and ONE run sequences. Utilizing this randomness we find additional new structure in de Bruijn sequences. We analyze binary sequences that are not de Bruijn but instead possess the sufficient structure so that every distinct binary n-tuple can be systematically "combed" out of the se- quence. These complete or nonclassical de Bruijn sequences are a generalization of the well-known de Bruijn cycle. Our investigation focuses on binary sequences, called double Eulerian cycles, that define a cycle along a graph (digraph) visiting each edge (arc) exactly twice. A new algorithm to generate a class of double Eulerian cycles on graphs and digraphs is found. Double Eulerian cycles along the binary Good - de Bruijn digraph are partitioned by the run structure of their defining sequences. This partition allows for a statistical analysis to determine the relative size of the set of complete cycles defined by the sequences we study. A measure that categorizes double Eulerian cycles along graphs (digraphs) by the distance between the two visitations of each edge (arc) is provided. An algorithm to generate double Eulerian cycles of minimum measure is given. Subjects: NA |
|
Language | English | |
Publication date |
June 1994 publication_date QS:P577,+1994-06-00T00:00:00Z/10 |
|
Current location |
IA Collections: navalpostgraduateschoollibrary; fedlink |
|
Accession number |
doubleeulericycl1094542901 |
|
Source | ||
Permission (Reusing this file) |
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States. |
Licensing
[edit]Public domainPublic domainfalsefalse |
This file is a work of a U.S. Army soldier or employee, taken or made as part of that person's official duties. As a work of the U.S. federal government, it is in the public domain in the United States.
العربية ∙ বাংলা ∙ català ∙ čeština ∙ Deutsch ∙ English ∙ español ∙ eesti ∙ فارسی ∙ suomi ∙ français ∙ hrvatski ∙ magyar ∙ Bahasa Indonesia ∙ italiano ∙ 日本語 ∙ 한국어 ∙ lietuvių ∙ македонски ∙ മലയാളം ∙ မြန်မာဘာသာ ∙ Nederlands ∙ polski ∙ português ∙ русский ∙ sicilianu ∙ српски / srpski ∙ Türkçe ∙ українська ∙ Tiếng Việt ∙ 中文(简体) ∙ 中文(繁體) ∙ +/− |
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 14:36, 17 July 2020 | 1,275 × 1,650, 147 pages (4.95 MB) | Fæ (talk | contribs) | FEDLINK - United States Federal Collection doubleeulericycl1094542901 (User talk:Fæ/IA books#Fork8) (batch 1993-2020 #14208) |
You cannot overwrite this file.
File usage on Commons
The following page uses this file:
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
Short title | Double Eulerian cycles on de Bruijn digraphs |
---|---|
Author | Krahn, Gary William |
Software used | Krahn, Gary William |
Conversion program | Adobe Acrobat 10.1.9 Paper Capture Plug-in |
Encrypted | no |
Page size |
|
Version of PDF format | 1.4 |