Greedy Universal Cycle Constructions for Weak Orders

Marsden Jacques; Dennis Wong

doi:10.1007/978-3-030-39219-2_29

Greedy Universal Cycle Constructions for Weak Orders

Marsden Jacques, Dennis Wong

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

A weak order is a way to rank n objects where ties are allowed. In this paper, we extend the prefer-larger and the prefer-opposite algorithms for de Bruijn sequences to provide the first known greedy universal cycle constructions for weak orders.

Original language	English
Title of host publication	Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings
Editors	Manoj Changat, Sandip Das
Publisher	Springer
Pages	363-370
Number of pages	8
ISBN (Print)	9783030392185
DOIs	https://doi.org/10.1007/978-3-030-39219-2_29
Publication status	Published - 2020
Externally published	Yes
Event	6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020 - Hyderabad, India Duration: 13 Feb 2020 → 15 Feb 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12016 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020
Country/Territory	India
City	Hyderabad
Period	13/02/20 → 15/02/20

Keywords

Greedy algorithm
Prefer-larger
Prefer-opposite
Universal cycle
Weak orders

Access to Document

10.1007/978-3-030-39219-2_29

Cite this

Jacques, M., & Wong, D. (2020). Greedy Universal Cycle Constructions for Weak Orders. In M. Changat, & S. Das (Eds.), Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings (pp. 363-370). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12016 LNCS). Springer. https://doi.org/10.1007/978-3-030-39219-2_29

Jacques, Marsden ; Wong, Dennis. / Greedy Universal Cycle Constructions for Weak Orders. Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings. editor / Manoj Changat ; Sandip Das. Springer, 2020. pp. 363-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8dea6fb708d74273acd2033da24e714c,

title = "Greedy Universal Cycle Constructions for Weak Orders",

abstract = "A weak order is a way to rank n objects where ties are allowed. In this paper, we extend the prefer-larger and the prefer-opposite algorithms for de Bruijn sequences to provide the first known greedy universal cycle constructions for weak orders.",

keywords = "Greedy algorithm, Prefer-larger, Prefer-opposite, Universal cycle, Weak orders",

author = "Marsden Jacques and Dennis Wong",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020 ; Conference date: 13-02-2020 Through 15-02-2020",

year = "2020",

doi = "10.1007/978-3-030-39219-2_29",

language = "English",

isbn = "9783030392185",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "363--370",

editor = "Manoj Changat and Sandip Das",

booktitle = "Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings",

address = "Germany",

}

Jacques, M & Wong, D 2020, Greedy Universal Cycle Constructions for Weak Orders. in M Changat & S Das (eds), Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12016 LNCS, Springer, pp. 363-370, 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020, Hyderabad, India, 13/02/20. https://doi.org/10.1007/978-3-030-39219-2_29

Greedy Universal Cycle Constructions for Weak Orders. / Jacques, Marsden; Wong, Dennis.
Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings. ed. / Manoj Changat; Sandip Das. Springer, 2020. p. 363-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12016 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Greedy Universal Cycle Constructions for Weak Orders

AU - Jacques, Marsden

AU - Wong, Dennis

PY - 2020

Y1 - 2020

N2 - A weak order is a way to rank n objects where ties are allowed. In this paper, we extend the prefer-larger and the prefer-opposite algorithms for de Bruijn sequences to provide the first known greedy universal cycle constructions for weak orders.

AB - A weak order is a way to rank n objects where ties are allowed. In this paper, we extend the prefer-larger and the prefer-opposite algorithms for de Bruijn sequences to provide the first known greedy universal cycle constructions for weak orders.

KW - Greedy algorithm

KW - Prefer-larger

KW - Prefer-opposite

KW - Universal cycle

KW - Weak orders

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

U2 - 10.1007/978-3-030-39219-2_29

DO - 10.1007/978-3-030-39219-2_29

M3 - Conference contribution

AN - SCOPUS:85079530158

SN - 9783030392185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 370

BT - Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings

A2 - Changat, Manoj

A2 - Das, Sandip

PB - Springer

T2 - 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020

Y2 - 13 February 2020 through 15 February 2020

ER -

Jacques M, Wong D. Greedy Universal Cycle Constructions for Weak Orders. In Changat M, Das S, editors, Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Proceedings. Springer. 2020. p. 363-370. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-39219-2_29

Greedy Universal Cycle Constructions for Weak Orders

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this