LCS Publication Details
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.