论文标题
嵌入式索引编码问题的缩小及其与两分图的连接性的关系
Minrank of Embedded Index Coding Problems and its Relation to Connectedness of a Bipartite Graph
论文作者
论文摘要
本文讨论了A. Porter和M. Wootters介绍的嵌入式索引编码问题（EICP），这是用户之间有侧面信息的分散通信问题。提出了与现有定义相比，EICP参数缩小的替代定义，该定义降低了计算复杂性。使用定向的双分图形（称为双方问题图形）给出了EICP的图形表示形式，仅使用一个称为侧面信息两部分图形的侧面信息来表示侧面信息。在SUICP的侧面信息图中类似的图形结构的启发下，图形结构与单个Unicast嵌入式索引编码问题（SUEICP）的侧面信息图中确定了类似于SUICP的周期和集团的图形结构。基于这些图形结构，称为树覆盖方案和双层覆盖方案的传输方案也针对SUEICP提出。同样，建立了侧面信息的连接性，两分图的连接性与EICP标量线性解决方案中所需的传输数量之间的关系。
This paper deals with embedded index coding problem (EICP), introduced by A. Porter and M. Wootters, which is a decentralized communication problem among users with side information. An alternate definition of the parameter minrank of an EICP, which has reduced computational complexity compared to the existing definition, is presented. A graphical representation for an EICP is given using directed bipartite graphs, called bipartite problem graph, and the side information alone is represented using an undirected bipartite graph called the side information bipartite graph. Inspired by the well-studied single unicast index coding problem (SUICP), graphical structures, similar to cycles and cliques in the side information graph of an SUICP, are identified in the side information bipartite graph of a single unicast embedded index coding problem (SUEICP). Transmission schemes based on these graphical structures, called tree cover scheme and bi-clique cover scheme are also presented for an SUEICP. Also, a relation between connectedness of the side information bipartite graph and the number of transmissions required in a scalar linear solution of an EICP is established.
