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
Adam Mickiewicz University
Technical University of Denmark, DTU