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

DOI10.1016/J.JDA.2014.06.003MaRDI QIDQ405571zbMATHOpenAlexFDO

Authors 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

necklaceminimum weightde Bruijn cycleFKM algorithmuniversal cycle

Mathematics Subject Classification ID

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

Recommendations

• Universal Cycles for Weight-Range Binary Strings
• De Bruijn sequences for fixed-weight binary strings
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Universal cycles for weak orders
• On universal cycles for new classes of combinatorial structures

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A problem in arrangements
• An Efficient Algorithm for Generating Necklaces with Fixed Density
• An algorithm for generating necklaces of beads in two colors
• Binary de Bruijn cycles under different equivalence relations
• De Bruijn sequences for fixed-weight binary strings
• De Bruijn sequences for the binary strings with maximum density
• Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
• Generating necklaces
• Graph-Theoretic Concepts in Computer Science
• Minimum Eulerian circuits and minimum de Bruijn sequences
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Normal Recurring Decimals
• On Universal Cycles for k-Subsets of an n-Set
• On universal cycles of labeled graphs
• Shorthand universal cycles for permutations
• Universal Cycles for Weight-Range Binary Strings
• Universal Cycles of Discrete Functions
• Universal cycles for combinatorial structures
• Universal cycles for permutations
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• Universal cycles of classes of restricted words

Cited in

(7)

• Constructing de Bruijn sequences by concatenating smaller universal cycles
• 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
• Universal Cycles for Weight-Range Binary Strings
• Properties of the cycles that contain all vectors of weight \(\le k\)
• Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence
• Investigating the discrepancy property of de Bruijn sequences

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

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