Universal cycles for weight-range binary strings

Joe Sawada; Aaron Williams; Dennis Wong

doi:10.1007/978-3-642-45278-9_33

Universal cycles for weight-range binary strings

Joe Sawada, Aaron Williams, Dennis Wong

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

10 Citations (Scopus)

Abstract

We present an efficient universal cycle construction for the set of binary strings of length n with weight (number of 1s) in the range c, c + 1,..., d where 0 ≤ c < d ≤ n. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using O(n) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.

Original language	English
Title of host publication	Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Pages	388-401
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-45278-9_33
Publication status	Published - 2013
Externally published	Yes
Event	24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France Duration: 10 Jul 2013 → 12 Jul 2013

Publication series

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

Conference

Conference	24th International Workshop on Combinatorial Algorithms, IWOCA 2013
Country/Territory	France
City	Rouen
Period	10/07/13 → 12/07/13

Access to Document

10.1007/978-3-642-45278-9_33

Cite this

Sawada, J., Williams, A., & Wong, D. (2013). Universal cycles for weight-range binary strings. In Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers (pp. 388-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8288 LNCS). https://doi.org/10.1007/978-3-642-45278-9_33

@inproceedings{5687be57e4b644a49fc1e851e7b46ef3,

title = "Universal cycles for weight-range binary strings",

abstract = "We present an efficient universal cycle construction for the set of binary strings of length n with weight (number of 1s) in the range c, c + 1,..., d where 0 ≤ c < d ≤ n. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using O(n) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.",

author = "Joe Sawada and Aaron Williams and Dennis Wong",

year = "2013",

doi = "10.1007/978-3-642-45278-9_33",

language = "English",

isbn = "9783642452772",

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

pages = "388--401",

booktitle = "Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers",

note = "24th International Workshop on Combinatorial Algorithms, IWOCA 2013 ; Conference date: 10-07-2013 Through 12-07-2013",

}

Sawada, J, Williams, A & Wong, D 2013, Universal cycles for weight-range binary strings. in Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8288 LNCS, pp. 388-401, 24th International Workshop on Combinatorial Algorithms, IWOCA 2013, Rouen, France, 10/07/13. https://doi.org/10.1007/978-3-642-45278-9_33

Universal cycles for weight-range binary strings. / Sawada, Joe; Williams, Aaron; Wong, Dennis.
Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers. 2013. p. 388-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8288 LNCS).

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

TY - GEN

T1 - Universal cycles for weight-range binary strings

AU - Sawada, Joe

AU - Williams, Aaron

AU - Wong, Dennis

PY - 2013

Y1 - 2013

N2 - We present an efficient universal cycle construction for the set of binary strings of length n with weight (number of 1s) in the range c, c + 1,..., d where 0 ≤ c < d ≤ n. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using O(n) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.

AB - We present an efficient universal cycle construction for the set of binary strings of length n with weight (number of 1s) in the range c, c + 1,..., d where 0 ≤ c < d ≤ n. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using O(n) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.

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

U2 - 10.1007/978-3-642-45278-9_33

DO - 10.1007/978-3-642-45278-9_33

M3 - Conference contribution

AN - SCOPUS:84893135699

SN - 9783642452772

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

SP - 388

EP - 401

BT - Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers

T2 - 24th International Workshop on Combinatorial Algorithms, IWOCA 2013

Y2 - 10 July 2013 through 12 July 2013

ER -

Universal cycles for weight-range binary strings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this