CaltechAUTHORS
  A Caltech Library Service

Edge removal in undirected networks

Langberg, Michael and Effros, Michelle (2020) Edge removal in undirected networks. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665

[img] PDF - Submitted Version
See Usage Policy.

362Kb

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 λ. 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
http://arxiv.org/abs/2005.10315arXivDiscussion Paper
ORCID:
AuthorORCID
Langberg, Michael0000-0002-7470-0718
Additional Information:This work is supported in part by NSF grants CCF-1817241 and CCF-1909451.
Funders:
Funding AgencyGrant Number
NSFCCF-1817241
NSFCCF-1909451
Record Number:CaltechAUTHORS:20200526-155245665
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200526-155245665
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:26 May 2020 22:55

Repository Staff Only: item control page