Interleaving Schemes on Circulant Graphs

Slivkins, A. and Bruck, J. (2002) Interleaving Schemes on Circulant Graphs. Technical Report. California Institute of Technology. [CaltechPARADISE:2002.ETR046]

Full text available as:

	PDF - Requires Adobe Acrobat Reader or other PDF viewer.
	Postscript - Requires a viewer, such as GhostView

Abstract

Interleaving schemes are used for error-correcting on a noisy channel. We consider interleaving schemes on infinite circulant graphs with two offsets 1 and d, with a goal to minimize the interleaving degree. Our constructions are minimal covers of the graph by copies of some subgraph S that can be labeled by a single label. We focus on minimizing the index of S - an 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 interleaving degree. We identify related combinatorial questions and advance conjectures.

EPrint Type:	Monograph (Technical Report)
Additional Information:	[Alternate URL: http://www.paradise.caltech.edu/papers/circ.ps]
Subjects:	All Records
ID Code:	58
Deposited By:	Jehoshua Bruck
Deposited On:	18 November 2002
Record Number:	CaltechPARADISE:2002.ETR046
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2002.ETR046
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record