Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids

DOI10.1109/TIT.2016.2555955zbMATH Open1359.94809arXiv1306.1157OpenAlexW1757164770MaRDI QIDQ2976716

Author name not available (Why is that?)

Publication date: 28 April 2017

Published in: (Search for Journal in Brave)

Abstract: Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding and representable discrete polymatroids. We consider vector linear solutions of networks over a field

m a t h b b F_{q},

with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. We define a extit{discrete polymatroidal} network and show that a linear fractional solution over a field

m a t h b b F_{q},

exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over

m a t h b b F_{q} .

An algorithm to construct networks starting from certain class of discrete polymatroids is provided. Every representation over

m a t h b b F_{q}

for the discrete polymatroid, results in a linear fractional solution over

m a t h b b F_{q}

for the constructed network. Next, we consider the index coding problem and show 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 extit{perfect linear index coding solution} for an index coding problem obtained from that matroid. 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.

Full work available at URL: https://arxiv.org/abs/1306.1157

Mathematics Subject Classification ID

No records found.

This page was built for publication: Linear Network Coding, Linear Index Coding and Representable Discrete Polymatroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976716)