Impact of a Single Edge on the Network Capacity
Author:
Eun Jee LeeMentor:
Michelle Effros, Professor of Electrical Engineering, California Institute of TechnologyFinding 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.