Network Coding and Matroid Theory

被引：27

作者：

Dougherty, Randall ^{[1
]}

Freiling, Chris ^{[2
]}

Zeger, Kenneth ^{[3
]}

机构：

[1] Ctr Commun Res, 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

来源：

PROCEEDINGS OF THE IEEE | 2011年 / 99卷 / 03期

基金：

美国国家科学基金会;

关键词：

Capacity; flow; information theory; matroid; multicast; network coding; polymatroid; ENTROPY;

D O I：

10.1109/JPROC.2010.2095490

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

Networks derived from matroids have played a fundamental role in proving theoretical results about the limits of network coding. In this tutorial paper, we review many connections between matroids and network coding theory, with specific emphasis on network solvability, admissible network alphabet sizes, linear coding, and network capacity.

引用

页码：388 / 405

页数：18

共 41 条

[1]

ADLER M, 2006, P ACM SIAM S, DOI DOI 10.1145/1109557.1109585

[2] Network information flow [J].

Ahlswede, R ;

Cai, N ;

Li, SYR ;

Yeung, RW .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216

[3] UNDECIDABILITY OF THE IDENTITY PROBLEM FOR FINITE-SEMIGROUPS [J].

ALBERT, D ;

BALDINGER, R ;

RHODES, J .

JOURNAL OF SYMBOLIC LOGIC, 1992, 57 (01) :179-192

[4]

[Anonymous], 1971, Combinatorial Mathematics and its Applications

[5]

[Anonymous], 1987, Combinatorial Geometries

[6]

[Anonymous], 2010, Matroid theory

[7]

BECKER T, 1993, GROOBNER BASES COMPU

[8]

Blumenthal L.M., 1961, MODERN VIEW GEOMETRY

[9] Network routing capacity [J].

Cannons, J ;

Dougherty, R ;

Freiling, C ;

Zeger, K .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (03) :777-788

[10] Dualities between entropy functions and network codes [J].

Chan, Terence ;

Grant, Alex .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (10) :4470-4487

← 1 2 3 4 5 →