Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2013 | public
Book Section - Chapter

Outer Bounds and a Functional Study of the Edge Removal Problem

Abstract

In this paper, we investigate the impact of a single edge on the capacity region of a network of error-free, point-to-point links. A family of networks and edges is said to exhibit the "edge removal property" if for any network and edge in the family, removing a δ-capacity edge changes the capacity region by at most δ in each dimension. We derive a sufficient condition on network coding functions to guarantee that the edge removal property holds when the network is operated using functions satisfying the condition. Also, we extend the family of network capacity bounds for which it is known that removing a single edge of capacity δ changes the capacity bound by at most f(δ) in each dimension. Specifically, we show that removing a single δ-capacity edge changes the Generalized Network Sharing outer bound by at most δ in each dimension and the Linear Programming outer bound by at most a constant times δ in each dimension.

Additional Information

© 2013 IEEE. This work was done while Michael Langberg was visiting California Institute of Technology. This material is based upon work supported by the National Science Foundation under Grant No. CCF-1018741, CCF-1038578 and by the Israel Science Foundation under grant 480/08.

Additional details

Created:
August 19, 2023
Modified:
October 26, 2023