Packing analogue of k-radius sequences

Zbigniew Lonc , Mirosław Truszczyński

Abstract

Niech k będzie liczbą naturalną. Ciągiem o promieniu k nad n-elementowym alfabetem A nazywamy ciąg, w którym każde dwa elementy alfabetu A występują co najmniej raz w odległości co najwyżej k. Problem skonstruowania najkrótszego możliwego ciągu o promieniu k, którego motywacje związane są z pewnymi problemami pojawiającymi się w przesyłaniu dużych zbiorów danych, był ostatnio badany przez kilku autorów. W pracy rozważa się obiekt dualny do ciągu o promieniu k, zwany upakowaniowym ciągiem o promieniu k. Jest to ciąg nad alfabetem A taki, że każde dwa elementy alfabetu A występują co najwyżej raz w odległości co najwyżej k. Tym razem interesuje nas możliwie najdłuższy taki ciąg. Podajemy konstrukcję asymptotycznie najdłuższego upakowaniowego ciągu o promieniu k dla każdego k=c*n^b, gdzie c i b są ustalonymi liczbami rzeczywistymi takimi, że c > 0, 0 leq b < 1 i b jest różne od 1/2.
Author Zbigniew Lonc ZAK
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
, Mirosław Truszczyński
Mirosław Truszczyński,,
-
Journal seriesEuropean Journal of Combinatorics, ISSN 0195-6698
Issue year2016
Vol57
Pages57-70
Publication size in sheets0.65
Keywords in Englishpacking k-radius sequence, ucycle packing, harmonious coloring of a graph
DOIDOI:10.1016/j.ejc.2016.04.004
URL http://www.sciencedirect.com/science/article/pii/S0195669816300063
Languageen angielski
Score (nominal)30
ScoreMinisterial score = 25.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 30.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.786 (2) - 2016=0.828 (5)
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


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