Linearity and solvability in multicast networks

被引:38
作者
Dougherty, R [1 ]
Freiling, C
Zeger, K
机构
[1] Commun Res Ctr, San Diego, CA 92121 USA
[2] Calif State Univ San Bernardino, Dept Math, San Bernardino, CA 92407 USA
[3] Univ Calif San Diego, Dept Elect & Comp Engn, La Jolla, CA 92093 USA
基金
美国国家科学基金会;
关键词
coding; flows; network information theory; routing;
D O I
10.1109/TIT.2004.834751
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
It is known that for every solvable multicast network,there exists a large enough finite-field alphabet such that a scalar linear solution exists. We prove: i) every binary solvable multicast network with at most two messages has a binary scalar linear solution; ii) for more than two messages, not every binary solvable multicast network has a binary scalar linear solution; iii) a multicast network that has a solution for a given alphabet might not have a solution for all larger alphabets.
引用
收藏
页码:2243 / 2256
页数:14
相关论文
共 19 条
[1]   Network information flow [J].
Ahlswede, R ;
Cai, N ;
Li, SYR ;
Yeung, RW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216
[2]  
Bose R. C., 1960, Transactions of the American Mathematics Society, V95, P191
[3]   ON THE FALSITY OF EULERS CONJECTURE ABOUT THE NON-EXISTENCE OF 2 ORTHOGONAL LATIN SQUARES OF ORDER 4T+2STAR [J].
BOSE, RC ;
SHRIKHANDE, SS .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1959, 45 (05) :734-737
[4]  
Bose RC., 1960, Can. J. Math, V12, P189, DOI [10.4153/CJM-1960-016-5, DOI 10.4153/CJM-1960-016-5]
[5]  
CHOU PA, 2003, P IEEE ALL C COMM CO
[6]  
FEDER M, 2003, EL C COMP COMPL ECCC, P1
[7]  
Ho T, 2003, 2003 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, P441
[8]  
Ho T, 2003, 2003 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, P442
[9]  
JAGGI S, UNPUB IEEE T INFORM
[10]   An algebraic approach to network coding [J].
Koetter, R ;
Médard, M .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2003, 11 (05) :782-795