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
![]() |
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: |
| |||||||||
ORCID: |
| |||||||||
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: |
| |||||||||
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