Constructions of asymptotically shortest k-radius sequences

Jerzy W. Jaromczyk, Zbigniew Lonc, Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f k(n) denote the length of a shortest k-radius sequence over A. We provide constructions demonstrating that (1) for every fixed k and for every fixed ε>0, f k(n)=1/2k n 2+O(n 1+ε) and (2) for every k=n α, where α is a fixed real such that 0<α<1, f k(n)=1/2k n 2+O(n β), for some β<2-α. Since f k(n)≥ 1/2k n 2-n/2k, the constructions give asymptotically optimal k-radius sequences. Finally, (3) we construct optimal 2-radius sequences for a 2p-element alphabet, where p is a prime.

Original languageEnglish
Pages (from-to)731-746
Number of pages16
JournalJournal of Combinatorial Theory. Series A
Volume119
Issue number3
DOIs
StatePublished - Apr 2012

Bibliographical note

Funding Information:
E-mail addresses: jurek@cs.uky.edu (J.W. Jaromczyk), zblonc@mini.pw.edu.pl (Z. Lonc), mirek@cs.uky.edu (M. Truszczyński). 1 Supported by the European Union in the framework of European Social Fund through the Warsaw University of Technology Development Programme.

Keywords

  • Cycle decompositions of graphs
  • K-radius sequences
  • Universal cycles

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Constructions of asymptotically shortest k-radius sequences'. Together they form a unique fingerprint.

Cite this