||Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem
||Harvey, Nicholas J.
||Robert D. Kleinberg, April Rasala Lehman
|LCS Document Number:
|Given a graph G = (V;E) and k source-sink 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 source-sink pair. In
the information °ow formulation, a vertex can transmit a function of the information it
received thereby allowing multiple source-sink 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  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