A Unification of Menger’s and Edmonds’ Theorems and Network Coding Theorems

The multicast capacity is the maximum rate that a sender can communicate common information to a set of receivers in a network. A fundamental theorem in graph theory by Menger determines the unicast capacity from a sender to a receiver; another fundamental theorem in graph theory by Edmonds determines the broadcast capacity from a sender to all other nodes. In both extreme cases, the multicast capacity can be achieved by routing, i.e., replicating or forwarding, information. Recent works on network information flow establish that the multicast capacity is equal to the minimum capacity of cuts separating the sender from a receiver, which can be achieved by performing network coding, while in general it cannot be achieved by routing.

We present a statement that unifies Menger’s Theorem, Edmonds’ Theorem, and network information flow theorems. Specifically, we show that the multicast capacity can be achieved by linear time-invariant network coding on Steiner edges (edges pointing into Steiner nodes) only. Our proof is constructive: a polynomial-time algorithm is presented that “hardwires” each non-Steiner edge with one of its predecessors while preserving the required connectivity from the sender to each receiver.

This is a joint work with Dr. Kamal Jain and Prof. Sun-Yuan Kung.

Speaker Details

Yunnan Wu received his B.Engr. degree in computer science from the University of Science and Technology of China, in 2000 and his M.A. degree in electrical engineering, from Princeton University, in 2002. He is currently a fourth year Ph.D. student in the Dept. of Electrical Engineering, Princeton University. He was with Microsoft Research, Asia, from 1999 to 2001 as a research assistant, with Bell Labs, Lucent Technologies as a summer intern in 2002, with Microsoft Research, Redmond, as a summer intern in 2003. His research interests include networking, graph theory, signal processing, wireless communications, and multimedia communications.

Date:
Speakers:
Yunnan Wu
Affiliation:
Princeton University
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Yunnan Wu

      Yunnan Wu