MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Polynomial time algorithms for network information flow

Sanders, Peter

December 2003, 15 pages.

Status: available - back from printing

The famous max-flow min-cut theorem states that a source node $s$ can send information through a network (V,E) to a sink node t at a rate determined by the min-cut separating s and t. Recently it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to reencode the information they receive. We give polynomial time algorithms for solving this problem. We additionally underline the potential benefit of coding by showing that multicasting without coding sometimes only allows a rate that is a factor Omega(log |V|) smaller.

  • Attachement: (316 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sanders, Peter},
  TITLE = {Polynomial time algorithms for network information flow},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-008},
  MONTH = {December},
  YEAR = {2003},
  ISSN = {0946-011X},