The lexicographically smallest universal cycle for binary strings with minimum specified weight

DOI10.1016/J.JDA.2014.06.003zbMath1306.68212OpenAlexW2066342920MaRDI QIDQ405571

Joe Sawada, Aaron Williams, Dennis Wong

Publication date: 5 September 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.06.003

zbMATH Keywords

minimum weightde Bruijn cycleFKM algorithmnecklaceuniversal cycle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Algorithms on strings (68W32)

Related Items (6)

A universal cycle for strings with fixed-content (which are also known as multiset permutations) ⋮ 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 ⋮ Properties of the cycles that contain all vectors of weight \(\le k\) ⋮ Investigating the discrepancy property of de Bruijn sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• Universal cycles of classes of restricted words
• Universal cycles for permutations
• Minimum Eulerian circuits and minimum de Bruijn sequences
• An algorithm for generating necklaces of beads in two colors
• Universal cycles for combinatorial structures
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Shorthand universal cycles for permutations
• Binary de Bruijn cycles under different equivalence relations
• On universal cycles of labeled graphs
• Universal Cycles for Weight-Range Binary Strings
• De Bruijn Sequences for Fixed-Weight Binary Strings
• An explicit universal cycle for the ( n -1)-permutations of an n -set
• De Bruijn Sequences for the Binary Strings with Maximum Density
• Universal Cycles of Discrete Functions
• Generating necklaces
• On Universal Cycles for k-Subsets of an n-Set
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• A problem in arrangements
• An Efficient Algorithm for Generating Necklaces with Fixed Density
• Graph-Theoretic Concepts in Computer Science
• Normal Recurring Decimals

This page was built for publication: The lexicographically smallest universal cycle for binary strings with minimum specified weight