A Caltech Library Service

Optimal Interleaving on Tori

Jiang, Anxiao (Andrew) and Cook, Matthew and Bruck, Jehoshua (2006) Optimal Interleaving on Tori. SIAM Journal on Discrete Mathematics, 20 (4). pp. 841-879. ISSN 0895-4801.

See Usage Policy.


Use this Persistent URL to link to this item:


This paper studies $t$-interleaving on two-dimensional tori. Interleaving has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. A $t$-interleaving of a graph is defined as a vertex coloring in which any connected subgraph of $t$ or fewer vertices has a distinct color at every vertex. We say that a torus can be perfectly t-interleaved if its t-interleaving number (the minimum number of colors needed for a t-interleaving) meets the sphere-packing lower bound, $\lceil t^2/2 \rceil$. We show that a torus is perfectly t-interleavable if and only if its dimensions are both multiples of $\frac{t^2+1}{2}$ (if t is odd) or t (if t is even). The next natural question is how much bigger the t-interleaving number is for those tori that are not perfectly t-interleavable, and the most important contribution of this paper is to find an optimal interleaving for all sufficiently large tori, proving that when a torus is large enough in both dimensions, its t-interleaving number is at most just one more than the sphere-packing lower bound. We also obtain bounds on t-interleaving numbers for the cases where one or both dimensions are not large, thus completing a general characterization of t-interleaving numbers for two-dimensional tori. Each of our upper bounds is accompanied by an efficient t-interleaving scheme that constructively achieves the bound.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:©2006 Society for Industrial and Applied Mathematics. Received by the editors November 10, 2004; accepted for publication (in revised form) May 15, 2006; published electronically December 5, 2006. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0208975. A one-page abstract presenting part of the results in this paper appeared in the Proceedings of the IEEE International Symposium on Information Theory, held in Chicago, 2004. The authors thank the anonymous reviewers for their very careful and thoughtful comments.
Subject Keywords:bursts, chromatic number, cluster, error-correcting code, Lee distance, multidimensional interleaving, t-interleaving, torus
Issue or Number:4
Record Number:CaltechAUTHORS:JIAsiamjdm06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7552
Deposited By: Archive Administrator
Deposited On:03 Mar 2007
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page