[Proceedings of the IEEE, March 2011, pp. 388-405 ]
Network Coding and Matroid Theory
Randall Dougherty, Chris Freiling, and Kenneth Zeger
Abstract
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.