Computer Science – Information Theory
Scientific paper
2010-10-04
Computer Science
Information Theory
8 pages, 12 figures, 48th Annual Allerton Conference on Communication, Control, and Computing, 2010
Scientific paper
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.
Effros Michelle
Ho Tracey
Jalali Shirin
No associations
LandOfFree
On Equivalence Between Network Topologies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Equivalence Between Network Topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Equivalence Between Network Topologies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275127