Interleaving Schemes on Circulant Graphs

Interleaving is used for error-correcting on a bursty noisy channel. Given a graph G describing the topology of the channel, we label the vertices of G so that each label-set is sufficiently sparse. The interleaving scheme corrects for any error burst of size at most t; it is a labeling where the distance between any two vertices in the same label-set is at least t. We consider interleaving schemes on infinite circulant graphs with two offsets 1 and d. In such graph the vertices are integers; edge ij exists if and only if ji ¡ jj 2 f1; dg. Our goal is to minimize the number of labels used. Our constructions are covers of the graph by the minimal number of translates of some labelset S. We focus on minimizing the index of S, which is the inverse of its density rounded up. We establish lower bounds and prove that our constructions are optimal or almost optimal, both for the index of S and for the number of labels.