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

研究成果: Article › 同行評審

6 引文斯高帕斯（Scopus）

摘要

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.

原文	English
文章編號	112022
期刊	Discrete Mathematics
卷	343
發行號	10
DOIs	https://doi.org/10.1016/j.disc.2020.112022
出版狀態	Published - 10月 2020
對外發佈	是

存取文件

10.1016/j.disc.2020.112022

其它文件與鏈接

Link to publication in Scopus

引用此

@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 BV",

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 - https://www.scopus.com/pages/publications/85086716696

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

摘要

存取文件

其它文件與鏈接

指紋

引用此