Efficient universal cycle constructions for weak orders

DOI10.1016/J.DISC.2020.112022MaRDI QIDQ785821zbMATH OpenOpenAlexFDO

Authors Joe Sawada, Dennis Wong

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.112022

zbMATH Keywords

Cayley permutationde Bruijn sequenceGray codesuccessor ruleuniversal cycleweak order

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Recommendations

• Greedy universal cycle constructions for weak orders
• Universal cycles for weak orders
• On the Weakness of an Ordered Set
• Universal cycles for permutations
• Universal cycles for combinatorial structures

Cites work

• A framework for constructing de Bruijn sequences via simple successor rules
• A Successor Rule Framework for Constructing $k$ -Ary de Bruijn Sequences and Universal Cycles
• Greedy universal cycle constructions for weak orders
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Lexicographically least circular substrings
• Research problems on Gray codes and universal cycles
• Universal cycles for weak orders
• Universal cycles of classes of restricted words

Cited in

(8)

• Universal cycles for weak orders
• Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random
• Efficient construction of long orientable sequences
• Constructing k-ary orientable sequences with asymptotically optimal length
• Efficient universal cycle constructions for k-permutations via concatenation trees
• Greedy universal cycle constructions for weak orders
• Generating Gray codes for weak orders in constant amortized time
• A universal cycle for strings with fixed-content (which are also known as multiset permutations)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Efficient universal cycle constructions for weak orders

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