On Equivalence Between Network Topologies

Abstract

One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.

8 pages, 12 figures, 48th Annual Allerton Conference on Communication, Control, and Computing, 2010

Cited by in corpus (10)

• Index Coding - An Interference Alignment Perspective
• On Multi-source Networks: Enumeration, Rate Region Computation, and Hierarchy
• The Unbounded Benefit of Encoder Cooperation for the $k$-user MAC
• On the Power of Cooperation: Can a Little Help a Lot? (Extended Version)
• A Local Perspective on the Edge Removal Problem
• Network Simplification in Half-Duplex: Building on Submodularity
• On the Cost and Benefit of Cooperation (Extended Version)
• On the Impact of a Single Edge on the Network Coding Capacity
• Towards an Operational Definition of Group Network Codes
• Can Negligible Cooperation Increase Network Capacity? The Average-Error Case