| Publication Title: |
Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| Publication Author: |
Harvey, Nicholas J. |
| Additional Authors: |
Robert D. Kleinberg, April Rasala Lehman |
| LCS Document Number: |
MIT-LCS-TR-964 |
| Publication Date: |
11-24-2004 |
| LCS Group: |
|
| Additional URL: |
|
| Abstract: |
| 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 [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.
|