MPI-I-2003-1-008

Polynomial time algorithms for network information flow

Sanders, Peter

MPI-I-2003-1-008. December 2003, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	316 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://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},}