Linear index coding and representable discrete polymatroids
Authors:
- 1 June 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 486-490
Abstract
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 ∈ R is specified by the tuple (x,H) where x ∈ X is the message demanded by R and H ⊆ X \ {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.Keywords
This publication has 13 references indexed in Scilit:
- A matroidal framework for network-error correcting codes2012
- On the Index Coding Problem and Its Relation to Network Coding and Matroid TheoryIEEE Transactions on Information Theory, 2010
- Efficient algorithms for Index Coding2008
- Index Coding with Side Information2006
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Linear network codingIEEE Transactions on Information Theory, 2003
- Discrete PolymatroidsJournal of Algebraic Combinatorics, 2002
- Network information flowIEEE Transactions on Information Theory, 2000
- Matroid representations by partitionsDiscrete Mathematics, 1999
- Almost Affine CodesDesigns, Codes and Cryptography, 1998