TY - GEN
T1 - Edge removal in undirected networks
AU - Langberg, Michael
AU - Effros, Michelle
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/7/12
Y1 - 2021/7/12
N2 - The edge-removal problem asks whether the removal of a \lambda-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than \lambda. We prove that for undirected networks, removing a \lambda capacity edge decreases the rate by O(\lambda. 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.
AB - The edge-removal problem asks whether the removal of a \lambda-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than \lambda. We prove that for undirected networks, removing a \lambda capacity edge decreases the rate by O(\lambda. 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.
UR - https://www.scopus.com/pages/publications/85115112233
U2 - 10.1109/ISIT45174.2021.9518243
DO - 10.1109/ISIT45174.2021.9518243
M3 - Conference contribution
AN - SCOPUS:85115112233
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1421
EP - 1426
BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021
Y2 - 12 July 2021 through 20 July 2021
ER -