Efficient universal cycle constructions for weak orders

Joe Sawada, Dennis Wong

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

A weak order is a way n competitors can rank in an event, where ties are allowed. A weak order can also be thought of as a relation on {1,2,…,n} that is transitive and complete. We provide the first efficient algorithms to construct universal cycles for weak orders by considering both rank and height representations. Each algorithm constructs the universal cycles in O(n) time per symbol using O(n) space.

Original languageEnglish
Article number112022
JournalDiscrete Mathematics
Volume343
Issue number10
DOIs
Publication statusPublished - Oct 2020
Externally publishedYes

Keywords

  • Cayley permutation
  • Gray code
  • Successor rule
  • Universal cycle
  • Weak order
  • de Bruijn sequence

Fingerprint

Dive into the research topics of 'Efficient universal cycle constructions for weak orders'. Together they form a unique fingerprint.

Cite this