CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665

[img] PDF - Submitted Version
See Usage Policy.

371kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665

Abstract

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
https://doi.org/10.1109/ISIT45174.2021.9518243DOIArticle
https://arxiv.org/abs/2005.10315arXivDiscussion Paper
ORCID:
AuthorORCID
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].
Funders:
Funding AgencyGrant Number
NSFCCF-1817241
NSFCCF-1909451
DOI:10.1109/ISIT45174.2021.9518243
Record Number:CaltechAUTHORS:20200526-155245665
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665
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
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 May 2020 22:55
Last Modified:29 Oct 2021 16:59

Repository Staff Only: item control page