References & Further Reading

References

  1. L. R. Ford Jr. and D. R. Fulkerson, Maximal Flow through a Network, 1956

    The original proof of the max-flow min-cut theorem. A foundational result in combinatorial optimization that established the duality between flows and cuts in directed graphs.

  2. R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, Network Information Flow, 2000

    The landmark paper that established network coding: coding at intermediate nodes achieves the max-flow min-cut bound for multicast. This paper opened an entire field of research.

  3. S.-Y. R. Li, R. W. Yeung, and N. Cai, Linear Network Coding, 2003

    Proves that linear codes over finite fields suffice for single-source multicast, reducing network coding to linear algebra. A key step toward practical implementations.

  4. R. Koetter and M. Médard, An Algebraic Approach to Network Coding, 2003

    Develops the algebraic framework for linear network coding, unifying the field with classical coding theory. Introduces the transfer matrix formulation used throughout this chapter.

  5. T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, A Random Linear Network Coding Approach to Multicast, 2006

    Shows that random linear network coding — where each node independently selects random coding coefficients — achieves the multicast capacity with high probability. Eliminates the need for centralized code design.

  6. R. Dougherty, C. Freiling, and K. Zeger, Insufficiency of Linear Coding in Network Information Flow, 2005

    The surprising result that linear codes are insufficient for some multi-source network coding problems. Uses matroid theory to construct examples where nonlinear codes strictly outperform linear codes.

  7. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, and J. Crowcroft, XORs in the Air: Practical Wireless Network Coding, 2006

    The COPE system: the first practical demonstration of network coding gains in wireless mesh networks. Shows 2–4x throughput improvement through opportunistic XOR coding at routers.

  8. S. El Rouayheb and A. Sprintson, On the Relation Between the Index Coding and the Network Coding Problems, 2010

    Establishes the equivalence between index coding and network coding. Any network coding problem can be reduced to an index coding instance and vice versa, unifying two seemingly different research directions.

  9. R. W. Yeung, Information Theory and Network Coding, Springer, 2008

    The most comprehensive textbook on network coding from an information-theoretic perspective. Covers single-source and multi-source problems, linear codes, and connections to matroid theory.

Further Reading

For readers who want to explore network coding beyond the foundational results.

  • Network coding for wireless networks

    C. Fragouli, J. Widmer, and J.-Y. Le Boudec, 'A Network Coding Approach to Energy-Efficient Broadcasting,' IEEE INFOCOM, 2006

    Shows how network coding reduces energy consumption in wireless broadcast by reducing the number of required transmissions. A good bridge from the noiseless theory in this chapter to practical wireless applications.

  • Compute-and-forward: network coding over noisy channels

    B. Nazer and M. Gastpar, 'Compute-and-Forward: Harnessing Interference Rather Than Avoiding It,' IEEE Trans. Inform. Theory, vol. 57, no. 10, 2011

    Extends network coding to noisy channels using lattice codes. Intermediate nodes decode integer linear combinations of transmitted codewords, bridging the gap between this chapter's noiseless results and the relay channel theory of Chapter 22.

  • Index coding and the information-theoretic limits

    Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, 'Index Coding with Side Information,' IEEE Trans. Inform. Theory, vol. 57, no. 3, 2011

    Provides the information-theoretic foundation for index coding, connecting it to graph entropy and linear programming bounds. Essential for understanding the open problems discussed in Section 21.3.

  • Non-Shannon inequalities and network coding

    Z. Zhang and R. W. Yeung, 'On Characterization of Entropy Function via Information Inequalities,' IEEE Trans. Inform. Theory, vol. 44, no. 4, 1998

    The first non-Shannon information inequality, which provides tighter outer bounds for some network coding problems than Shannon-type inequalities alone. Opens the fascinating question of whether the capacity of all networks can be characterized using only classical entropy inequalities.

  • Coded caching as network coding

    M. A. Maddah-Ali and U. Niesen, 'Fundamental Limits of Caching,' IEEE Trans. Inform. Theory, vol. 60, no. 5, pp. 2856–2867, 2014

    The foundational coded caching paper, which can be viewed as applying network coding to content distribution with caches. The coded multicasting gain is a direct consequence of the network coding principle: coded messages serve multiple users through their different side information. See Chapter 27 for the full treatment.

ExercisesCh 22 →