A Caltech Library Service

A Local Perspective on the Edge Removal Problem

Wei, Fei and Langberg, Michael and Effros, Michelle (2019) A Local Perspective on the Edge Removal Problem. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 191-195. ISBN 9781538692912.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge e^∗ with capacity R_(e^∗) reduces the achievable rate on each source by no more than R_(e^∗). In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a local perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge e^∗. Our central results give sufficient conditions on the function carried by edge e^∗ in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e^∗ is removed.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2019 IEEE. Work supported in part by NSF grants CCF-1526771, CCF-1527524 and CCF-1817241.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20191004-100329963
Persistent URL:
Official Citation:F. Wei, M. Langberg and M. Effros, "A Local Perspective on the Edge Removal Problem," 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 191-195. doi: 10.1109/ISIT.2019.8849282
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99071
Deposited By: George Porter
Deposited On:04 Oct 2019 20:06
Last Modified:16 Nov 2021 17:43

Repository Staff Only: item control page