Linear Index Coding and Representable Discrete Polymatroids
Data(s) |
2014
|
---|---|
Resumo |
Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections between linear index coding and representable discrete polymatroids. The index coding problem involves a sender which generates a set of messages X = {x(1), x(2), ... x(k)} and a set of receivers R which demand messages. A receiver R is an element of R is specified by the tuple (x, H) where x. X is the message demanded by R and H subset of X \textbackslash {x} is the side information possessed by R. It is first shown that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. Multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/51006/1/iee_int_sym_inf_486_2014.pdf Muralidharan, Vijayvaradharaj T and Rajan, Sundar V (2014) Linear Index Coding and Representable Discrete Polymatroids. In: IEEE International Symposium on Information Theory (ISIT), JUN 29-JUL 04, 2014, Honolulu, HI, pp. 486-490. |
Publicador |
IEEE |
Relação |
http://10.1109/ISIT.2014.6874880 http://eprints.iisc.ernet.in/51006/ |
Palavras-Chave | #Electrical Communication Engineering |
Tipo |
Conference Proceedings NonPeerReviewed |