Efficient universal cycle constructions for weak orders

Joe Sawada; Dennis Wong

doi:10.1016/j.disc.2020.112022

Efficient universal cycle constructions for weak orders

Joe Sawada, Dennis Wong

Research output: Contribution to journal › Article › peer-review

4 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 language	English
Article number	112022
Journal	Discrete Mathematics
Volume	343
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2020.112022
Publication status	Published - Oct 2020
Externally published	Yes

Keywords

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

Access to Document

10.1016/j.disc.2020.112022

Cite this

@article{3bc5939b1ca341739a3e21adbc10342b,

title = "Efficient universal cycle constructions for weak orders",

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.",

keywords = "Cayley permutation, Gray code, Successor rule, Universal cycle, Weak order, de Bruijn sequence",

author = "Joe Sawada and Dennis Wong",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = oct,

doi = "10.1016/j.disc.2020.112022",

language = "English",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - Efficient universal cycle constructions for weak orders

AU - Sawada, Joe

AU - Wong, Dennis

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

KW - Cayley permutation

KW - Gray code

KW - Successor rule

KW - Universal cycle

KW - Weak order

KW - de Bruijn sequence

UR - http://www.scopus.com/inward/record.url?scp=85086716696&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2020.112022

DO - 10.1016/j.disc.2020.112022

M3 - Article

AN - SCOPUS:85086716696

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 112022

ER -

Efficient universal cycle constructions for weak orders

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this