De Bruijn Sequences for Fixed-Weight Binary Strings

DOI10.1137/100808782zbMath1248.68363OpenAlexW2045924045MaRDI QIDQ2910938

Frank Ruskey, Aaron Williams, Joe Sawada

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

maximum weightlexicographically least de Bruijn sequence

Mathematics Subject Classification ID

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

Related Items (15)

A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ Finding the largest fixed-density necklace and Lyndon word ⋮ Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles ⋮ Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence ⋮ Constructing de Bruijn sequences by concatenating smaller universal cycles ⋮ A Gray code for fixed-density necklaces and Lyndon words in constant amortized time ⋮ Properties of the cycles that contain all vectors of weight \(\le k\) ⋮ The lexicographically smallest universal cycle for binary strings with minimum specified weight ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ Successor rules for flipping pancakes and burnt pancakes ⋮ Binary bubble languages and cool-lex order ⋮ The coolest way to generate binary strings ⋮ De Bruijn Sequences for the Binary Strings with Maximum Density ⋮ Investigating the discrepancy property of de Bruijn sequences ⋮ Bubble-flip -- a new generation algorithm for prefix normal words

This page was built for publication: De Bruijn Sequences for Fixed-Weight Binary Strings