Published January 1, 2002
| public
Report
Open
Interleaving Schemes on Circulant Graphs
- Creators
- Slivkins, Aleksandrs
- Bruck, Jehoshua
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.
Files
etr046.pdf
Files
(3.9 MB)
Name | Size | Download all |
---|---|---|
md5:80319a48dedc014d37537c4b23631f0f
|
1.2 MB | Download |
md5:57d0c8b81c9240908e2a97feaedfdddd
|
2.8 MB | Preview Download |
Additional details
- Eprint ID
- 26076
- Resolver ID
- CaltechPARADISE:2002.ETR046
- Created
-
2002-11-18Created from EPrint's datestamp field
- Updated
-
2019-11-22Created from EPrint's last_modified field
- Caltech groups
- Parallel and Distributed Systems Group