A unification of network coding and tree-packing (routing) theorems

Yunnan Wu, Kamal Jain, Sun Yuan Kung

Research output: Contribution to journalArticle

39 Scopus citations

Abstract

Given a network of lossless links with rate constraints, a source node, and a set of destination nodes, the multicast capacity is the maximum rate at which the source can transfer common information to the destinations. The multicast capacity cannot exceed the capacity of any cut separating the source from a destination; the minimum of the cut capacities is called the cut bound. A fundamental theorem in graph theory by Edmonds established that if all nodes other than the source are destinations, the cut bound can be achieved by routing. In general, however, the cut bound cannot be achieved by routing. Ahlswede et al. established that the cut bound can be achieved by performing network coding, which generalizes routing by allowing information to be mixed. This paper presents a unifying theorem that includes Edmonds' theorem and Ahlswede et al.'s theorem as special cases. Specifically, it shows that the multicast capacity can still be achieved even if information mixing is only allowed on edges entering relay nodes. This unifying theorem is established via a graph theoretic hardwiring theorem, together with the network coding theorems for multicasting. The proof of the hardwiring theorem implies a new proof of Edmonds' theorem.

Original languageEnglish (US)
Pages (from-to)2398-2409
Number of pages12
JournalIEEE Transactions on Information Theory
Volume52
Issue number6
DOIs
StatePublished - Jun 1 2006

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Flow
  • Multicast
  • Network coding
  • Routing
  • Steiner tree

Fingerprint Dive into the research topics of 'A unification of network coding and tree-packing (routing) theorems'. Together they form a unique fingerprint.

  • Cite this