De Bruijn sequences for fixed-weight binary strings

DOI10.1137/100808782MaRDI QIDQ2910938zbMATH OpenOpenAlexFDO

Authors Frank Ruskey, Joe Sawada, Aaron Williams

Publication date 12 September 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/0516c1f1d7d599bc311ff06c510d97e7495f72d2

zbMATH Keywords

lexicographically least de Bruijn sequencemaximum weight

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• The coolest way to generate binary strings
• De Bruijn sequences for the binary strings with maximum density
• A surprisingly simple de Bruijn sequence construction
• Further results on the Bruijn weight classes
• scientific article; zbMATH DE number 2141530

Cited in

(25)

• Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence
• Constructing de Bruijn sequences by concatenating smaller universal cycles
• Enumerating lambda terms by weighted length of their de Bruijn representation
• Storage efficient decoding for a class of binary de Bruijn sequences
• Investigating the discrepancy property of de Bruijn sequences
• Finding the largest fixed-density necklace and Lyndon word
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Properties of the cycles that contain all vectors of weight k
• The grandmama de Bruijn sequence for binary strings
• Universal Cycles for Weight-Range Binary Strings
• De Bruijn sequences for the binary strings with maximum density
• scientific article; zbMATH DE number 5016615 (Why is no real title available?)
• Cryptographically Strong de Bruijn Sequences with Large Periods
• A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• de Bruijn notation as a nested datatype
• The coolest way to generate binary strings
• Sequences of binary strings with relation of conditional simplicity
• Bubble-flip -- a new generation algorithm for prefix normal words
• Constructing the first (and coolest) fixed-content universal cycle
• Binary bubble languages and cool-lex order
• Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random
• Universal cycle constructions for k-subsets and k-multisets
• A universal cycle for strings with fixed-content (which are also known as multiset permutations)
• Successor rules for flipping pancakes and burnt pancakes

This page was built for publication: De Bruijn sequences for fixed-weight binary strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910938)