A Caltech Library Service

Edge removal in undirected networks

Langberg, Michael and Effros, Michelle (2021) Edge removal in undirected networks. In: 2021 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 1421-1426. ISBN 978-1-5386-8209-8.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The edge-removal problem asks whether the removal of a λ-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than λ. We prove that for undirected networks, removing a λ capacity edge decreases the rate by O(λ). Through previously known reductive arguments, here newly applied to undirected networks, our result implies that the zero-error capacity region of an undirected network equals its vanishing-error capacity region. Whether it is possible to prove similar results for directed networks remains an open question.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Langberg, Michael0000-0002-7470-0718
Additional Information:© 2021 IEEE. This work is supported in part by NSF grants CCF-1817241 and CCF-1909451. The full version of this work appears in [1].
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20200526-155245665
Persistent URL:
Official Citation:M. Langberg and M. Effros, "Edge removal in undirected networks," 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 1421-1426, doi: 10.1109/ISIT45174.2021.9518243
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103480
Deposited By: Tony Diaz
Deposited On:26 May 2020 22:55
Last Modified:29 Oct 2021 16:59

Repository Staff Only: item control page