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 -