Record Details

On the Varshamov-Tenengolts construction on binary strings

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On the Varshamov-Tenengolts construction on binary strings
 
Creator KULKARNI, AA
KIYAVASH, N
SREENIVAS, R
 
Subject Deletion channel
Varshamov-Tenengolts codes
Single-deletion-correcting codes
Hypergraphs
Coding theory
CORRECTING CODES
DELETION
CHANNELS
 
Description This paper is motivated by the problem of finding the largest single-deletion-correcting code for binary strings. The Varshamov-Tenengolts construction classifies binary strings into non-overlapping sets, the largest set of these is asymptotically the largest singledeletion-correcting code. However despite the asymptotic optimality little is known about the quality of the construction as a function of the string length. We show that these sets are also responsible for the (near) solution of several combinatorial problems on a certain hypergraph. Furthermore our results are valid for any string length. We show that the sets collectively solve strong vertex coloring and edge coloring on the hypergraph exactly. For any string length n we show that the largest of these sets is within n+1/n-1 of optimal matching on the hypergraph, which also corresponds to the largest single-deletion-correcting code. Moreover, we show for any n the smallest of these sets is within n(2)-n/n(2)-3n+4-4/2(n) of the smallest cover of this hypergraph and that each of these sets is a perfect matching. We then obtain similar results on the dual of this hypergraph. (C) 2013 Elsevier B.V. All rights reserved.
 
Publisher ELSEVIER SCIENCE BV
 
Date 2014-12-28T15:16:26Z
2014-12-28T15:16:26Z
2014
 
Type Article
 
Identifier DISCRETE MATHEMATICS, 31779-90
0012-365X
1872-681X
http://dx.doi.org/10.1016/j.disc.2013.11.003
http://dspace.library.iitb.ac.in/jspui/handle/100/16849
 
Language English