A Caltech Library Service

Edge removal in undirected networks

Langberg, Michael and Effros, Michelle (2020) Edge removal in undirected networks. . (Unpublished)

[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 λ. In this short manuscript, 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Langberg, Michael0000-0002-7470-0718
Additional Information:This work is supported in part by NSF grants CCF-1817241 and CCF-1909451.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20200526-155245665
Persistent URL:
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:26 May 2020 22:55

Repository Staff Only: item control page