Universal cycles for weight-range binary strings

Joe Sawada, Aaron Williams, Dennis Wong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 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 languageEnglish
Title of host publicationCombinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers
Pages388-401
Number of pages14
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France
Duration: 10 Jul 201312 Jul 2013

Publication series

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

Conference

Conference24th International Workshop on Combinatorial Algorithms, IWOCA 2013
Country/TerritoryFrance
CityRouen
Period10/07/1312/07/13

Fingerprint

Dive into the research topics of 'Universal cycles for weight-range binary strings'. Together they form a unique fingerprint.

Cite this