Constructions of short k-radius sequences

Graphs, Hypergraphs, and Computing

13 March 15:30 - 16:30

Zbigniew Lonc - Warsaw University of Technology

A sequence over a finite alphabet is a k-radius sequence if every two elements of the alphabet are within distance at most k at least once somewhere in the sequence. These sequences were introduced to model a caching strategy for computing certain functions on large data sets. We shall present some constructions of k-radius sequences of asymptotically shortest length. We shall also discuss some generalizations of this problem and its connections to other combinatorial problems such as achromatic and harmonious colorings of graphs and hypergraphs.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to