Impact of a Single Edge on the Network Capacity
Author:Eun Jee Lee
Mentor:Michelle Effros, Professor of Electrical Engineering, California Institute of Technology
Finding the capacity region of a general multi-source multi-demand network is often a hard problem. Understanding how much difference a single edge can make in the capacity of a large network is important for developing systematic tools for bounding the capacities of such networks. In this study, we investigate the impact on the network capacity of a single edge connected to a terminal edge. We then extend the result to find a condition on the network under which we can bound the impact of removing a single edge. Also, we find a multiplicative bound rather than an additive bound on the impact of removing a single edge which the upper and lower bounding network topologies are the same.