| Paper ID | D3-S7-T1.3 |
| Paper Title |
Edge removal in undirected networks |
| Authors |
Michael Langberg, University at Buffalo, United States; Michelle Effros, Caltech, United States |
| Session |
D3-S7-T1: Topics in Network Coding II |
| Chaired Session: |
Thursday, 15 July, 00:00 - 00:20 |
| Engagement Session: |
Thursday, 15 July, 00:20 - 00:40 |
| Abstract |
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.
|
