Graph-Theoretic Approaches to Two-Sender Index Coding

Abstract

Consider a communication scenario over a noiseless channel where a sender is required to broadcast messages to multiple receivers, each having side information about some messages. In this scenario, the sender can leverage the receivers' side information during the encoding of messages in order to reduce the required transmissions. This type of encoding is called index coding. In this paper, we study index coding with two cooperative senders, each with some subset of messages, and multiple receivers, each requesting one unique message. The index coding in this setup is called two-sender unicast index coding (TSUIC). The main aim of TSUIC is to minimize the total number of transmissions required by the two senders. Based on graph-theoretic approaches, we prove that TSUIC is equivalent to single-sender unicast index coding (SSUIC) for some special cases. Moreover, we extend the existing schemes for SSUIC, viz., the cycle-cover scheme, the clique-cover scheme, and the local-chromatic scheme to the corresponding schemes for TSUIC.

To be presented at 2016 IEEE Global Communications Conference (GLOBECOM 2016) Workshop on Network Coding and Applications (NetCod), Washington, USA, 2016

References in corpus (3)

• The Single-Uniprior Index-Coding Problem: The Single-Sender Case and The Multi-Sender Extension
• Linear Codes are Optimal for Index-Coding Instances with Five or Fewer Receivers
• Generalized Interlinked Cycle Cover for Index Coding

Cited by in corpus (7)

• Cooperative Multi-Sender Index Coding
• Structural Characteristics of Two-Sender Index Coding
• Linear Index Coding With Multiple Senders and Extension to a Cellular Network
• Optimal Scalar Linear Codes for Some Classes of The Two-Sender Groupcast Index Coding Problem
• Optimal Linear Broadcast Rates of the Two-Sender Unicast Index Coding Problem with Fully-Participated Interactions
• Capacity Theorems for Distributed Index Coding
• On the Capacity for Distributed Index Coding