{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:12Z","timestamp":1787319852931,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>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 \u201cshort\u201d $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.<\/jats:p>","DOI":"10.1137\/15m1023506","type":"journal-article","created":{"date-parts":[[2016,3,10]],"date-time":"2016-03-10T10:54:00Z","timestamp":1457607240000},"page":"452-464","source":"Crossref","is-referenced-by-count":6,"title":["Constructing Optimal $k$-Radius Sequences"],"prefix":"10.1137","volume":"30","author":[{"given":"Adrian","family":"Bondy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zbigniew","family":"Lonc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Rza\u0345\u017cewski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,3,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90187-5"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.08.004"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02510-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02473-7"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2014.04.005"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360991"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.10.010"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. Jaromczyk and Z. Lonc,\n                      Sequences of radius $k$: How to fetch many huge objects into small memory for pairwise computations\n                      , in Proceedings of ISAAC 2004, Lecture Notes in Comput. Sci. 3341, Springer, New York, 2004, pp. 594-605.","DOI":"10.1007\/978-3-540-30551-4_52"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.11.009"},{"key":"atypb10","first-page":"1856","volume":"9","author":"Kirkman T.P.","journal-title":"Trans. Hist. Soc. Lancashire Cheshire"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1938-1501951-4"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1023506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:19Z","timestamp":1787316799000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1023506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M1023506"],"URL":"https:\/\/doi.org\/10.1137\/15m1023506","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}