Publication Title: 
Comparing Network Coding with Multicommodity Flow for the kpairs Communication Problem 
Publication Author: 
Harvey, Nicholas J. 
Additional Authors: 
Robert D. Kleinberg, April Rasala Lehman 
LCS Document Number: 
MITLCSTR964 
Publication Date: 
11242004 
LCS Group: 

Additional URL: 

Abstract: 
Given a graph G = (V;E) and k sourcesink pairs of vertices, this papers investigates
the maximum rate r at which all pairs can simultaneously communicate. We view this
problem from two perspectives and compare their advantages. In the multicommodity °ow
formulation, a solution provides dedicated bandwidth r between each sourcesink pair. In
the information °ow formulation, a vertex can transmit a function of the information it
received thereby allowing multiple sourcesink pairs to share bandwidth. For directed acyclic
graphs with n vertices, we show that the rate achievable in the information °ow formulation
can be a multiplicative factor n larger than the rate achievable in the multicommodity
°ow formulation. It is well known [5] that for undirected graphs with n vertices, in the
multicommodity °ow formulation, the maximum rate achievable can be an O(1= logjV j)
multiplicative factor smaller than the value of the sparsest cut. We extend this result to show
that the maximum rate achievable in the information °ow setting can be an O(1= logjV j)
multiplicative factor smaller than the sparsest cut value.
For directed acyclic graphs G, we deŻne a parameter called the value of the most meager
cut which is an upper bound for the maximum rate achievable in the information °ow setting.
We also present an example illustrating that this upper bound is not always tight. 
To obtain this publication: 

To purchase a printed copy of this publication please contact
MIT
Document Services.
