Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles

zbMath1330.05007MaRDI QIDQ2635088

Aaron Williams, Dennis Wong, Joe Sawada

Publication date: 11 February 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p24

zbMATH Keywords

greedy algorithmde Bruijn sequencenecklacesFKM algorithmuniversal cyclelexicographical ordering\(k\)-suffix language

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05)

Related Items (8)

A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence ⋮ Properties of the cycles that contain all vectors of weight \(\le k\) ⋮ Constructing the first (and coolest) fixed-content universal cycle ⋮ Classifying rotationally-closed languages having greedy universal cycles ⋮ Necklaces and bracelets in R ⋮ Circular slider graphs: de Bruijn, Kautz, Rauzy, lamplighters and spiders ⋮ On greedy algorithms for binary de Bruijn sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Number of cycles in the graph of 312-avoiding permutations
• The coolest way to generate binary strings
• Sandpile groups and spanning trees of directed line graphs
• Binary bubble languages and cool-lex order
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• Universal cycles of classes of restricted words
• Special issue: Generalisations of de Bruijn cycles and gray codes. Papers from the Banff International Research Station (BIRS) workshop, Banff, Canada, December 5--9, 2004
• Universal cycles for permutations
• An algorithm for generating necklaces of beads in two colors
• Universal cycles for combinatorial structures
• A class of nonlinear de Bruijn cycles
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Shorthand universal cycles for permutations
• On the theorem of Fredricksen and Maiorana about de Bruijn sequences
• D2B: A de Bruijn based content-addressable network
• On universal cycles of labeled graphs
• Generalized de Bruijn words for primitive words and powers
• Universal Cycles for Weight-Range Binary Strings
• De Bruijn Sequences for Fixed-Weight Binary Strings
• Universal Cycles of Discrete Functions
• Generating necklaces
• On Universal Cycles for k-Subsets of an n-Set
• A problem in arrangements
• The lexicographically least de Bruijn cycle

This page was built for publication: Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles