Constructing optimal k-radius sequences

Adrian Bondy , Zbigniew Lonc , Paweł Rzążewski

Abstract

A $k$-radius sequence over an $n$-element alphabet $A$ is a sequence in which every two elements of $A$ appear within distance at most $k$ (where the distance is defined as the difference of indices). By a $k$-radius sequence over an $n$-element alphabet $A$ we mean a sequence in which every two elements of $A$ appear within distance at most $k$. The problem of constructing shortest possible $k$-radius sequences, motivated by some problems occurring in large data transfer, has been studied by several authors recently. In this paper we present an explicit construction of “short” $k$-radius sequences for some values of $k$ and $n$. This construction allows us to find 2-radius sequences of the shortest possible length for all but very special values of $n$. For all $n$ we construct 2-radius sequences whose length differs from the length of the shortest one only by a constant. Moreover, we construct shortest possible $k$-radius sequences when $n=2k^2+2k+1$ and $k$ is a power of a prime. Our construction depends on the existence of some other sequences that we call $k$-perfect and $k$-additive. We investigate these sequences as they seem to be interesting in themselves.
Author Adrian Bondy
Adrian Bondy,,
-
, Zbigniew Lonc ZAK
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski ZZIMN
Paweł Rzążewski,,
- Department of Applied Computer Science and Computation Methods
Journal seriesSiam Journal on Discrete Mathematics, ISSN 0895-4801
Issue year2016
Vol30
No1
Pages452-464
Publication size in sheets0.6
Keywords in Englishk-radius sequences, k-additive sequences, k-perfect sequences, sequentially additive labelings of graphs
Abstract in PolishCiąg o promieniu k nad n-elementowym alfabetem A jest to ciąg, w którym każde dwa elementy z A pojawiają się w odległości co najwyżej k (gdzie odległość jest zdefiniowana jako różnica indeksów wyrazów ciągu). Problem konstruowania możliwie krótkich ciągów o promieniu k jest motywowany pewnymi problemami pojawiającymi się w przesyłaniu dużych zbiorów danych. W pracy znajdujemy konstrukcje “krótkich” ciągów o promieniu k dla pewnych wartości n i k. Ta konstrukcja pozwala znaleźć najkrótsze ciągi o promieniu 2 dla wszystkich, poza bardzo szczególnymi, wartości n. Dla wszystkich wartości konstruujemy ciągi o promieniu 2, których długość różni się od długości najkrótszego ciągu tylko o stałą. Ponadto, konstruujemy najkrótsze możliwe ciągi o promieniu k dla n=2k^2+2k+1 i k będącego potęgą liczby pierwszej. Nasza konstrukcja zależy od istnienia pewnych ciągów zwanych k-doskonałymi i k-addytywnymi. Badamy własności również tych ciągów.
DOIDOI:10.1137/15M1023506
URL http://epubs.siam.org/doi/abs/10.1137/15M1023506
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.755 (2) - 2016=0.88 (5)
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back