A Local Perspective on the Edge Removal Problem
- Creators
- Wei, Fei
- Langberg, Michael
- Effros, Michelle
Abstract
The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge e^∗ with capacity R_(e^∗) reduces the achievable rate on each source by no more than R_(e^∗). In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a local perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge e^∗. Our central results give sufficient conditions on the function carried by edge e^∗ in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e^∗ is removed.
Additional Information
© 2019 IEEE. Work supported in part by NSF grants CCF-1526771, CCF-1527524 and CCF-1817241.Attached Files
Submitted - 1907.01133.pdf
Files
Name | Size | Download all |
---|---|---|
md5:37ffd2a10bcd0b7a628d29eb12cc9b37
|
613.4 kB | Preview Download |
Additional details
- Eprint ID
- 99071
- DOI
- 10.1109/isit.2019.8849282
- Resolver ID
- CaltechAUTHORS:20191004-100329963
- CCF-1526771
- NSF
- CCF-1527524
- NSF
- CCF-1817241
- NSF
- Created
-
2019-10-04Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field