Optimal Index Codes With Near-Extreme Rates

被引:24
作者
Dau, Son Hoang [1 ]
Skachek, Vitaly [2 ]
Chee, Yeow Meng [1 ]
机构
[1] Nanyang Technol Univ, Sch Phys & Math Sci, Div Math Sci, Singapore 637371, Singapore
[2] Univ Illinois, Coordinated Sci Lab, Urbana, IL 61801 USA
基金
新加坡国家研究基金会;
关键词
Index coding; network coding; side information; broadcast; NETWORK; BROADCAST; CIRCUITS; THEOREM; DEMAND; ISCOD;
D O I
10.1109/TIT.2013.2295331
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this paper, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. In addition, a circuit-packing bound is revisited, and several families of digraphs, optimal with respect to this bound, whose min-ranks can be found in polynomial time, are presented.
引用
收藏
页码:1515 / 1527
页数:13
相关论文
共 40 条
[31]   A MINIMAX ARC THEOREM FOR REDUCIBLE FLOW-GRAPHS [J].
RAMACHANDRAN, V .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (04) :554-560
[32]   Packing circuits in eulerian digraphs [J].
Seymour, PD .
COMBINATORICA, 1996, 16 (02) :223-231
[33]   THE BANDWAGON [J].
SHANNON, CE .
IRE TRANSACTIONS ON INFORMATION THEORY, 1956, 2 (01) :3-3
[35]  
Szwarcfiter J. L., 1989, GRAPHS ALGORITHMS, V89, P153
[36]  
Tarjan R., 1972, SIAM Journal on Computing, V1, P146, DOI 10.1137/0201010
[37]  
Traskov D, 2009, GLOB TELECOMM CONF, P3835
[38]   FEEDBACK VERTEX SETS AND CYCLICALLY REDUCIBLE GRAPHS [J].
WANG, CC ;
LLOYD, EL ;
SOFFA, ML .
JOURNAL OF THE ACM, 1985, 32 (02) :296-313
[39]  
West D. B., 2006, INTRO GRAPH THEORY
[40]  
Zhang C., 2010, INFOCOM, 2010 Proceedings IEEE, P1