Interleaving schemes on circulant graphs with two offsets
- Creators
- Slivkins, Aleksandrs
- Bruck, Jehoshua
Abstract
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 a graph the vertices are integers; edge ij exists if and only if |i−j|∈{1,d}. 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 label-set 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.
Additional Information
Copyright © 2009 Elsevier. Received 30 July 2007; revised 15 October 2008; accepted 23 January 2009. Available online 28 February 2009. The authors are most grateful to the anonymous referees for their comments. This research has been completed while the first author was a B.S. student at California Institute of Technology and a Ph.D. student at Cornell University.Additional details
- Eprint ID
- 16055
- DOI
- 10.1016/j.disc.2009.01.020
- Resolver ID
- CaltechAUTHORS:20090925-102048176
- Created
-
2009-10-07Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field