MPI-I-2003-1-008
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: MPI-I-2003-1-008.ps (316 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-008
BibTeX
@TECHREPORT{Sanders2003,
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},
}