Description

The concept that the undirected multiple-unicast network information capacity is the same as the routing capacity is one of the major open questions in information theory. This concept is only supported by a small number of networks and network classes. The sparsest cut bound and the linear programming bound are the only two explicit upper constraints on information capacity that are known for broad undirected networks. In this book, we provide the partition bound, an information-theoretic upper bound on the generic undirected multiple-unicast networks' capacity.

It's demonstrated the NP-completeness of the choice version issue for computing the bound. Here offered two types of undirected multiple-unicast networks that can be routed to achieve the partition bound. The concept is thus established for various groups of networks. The conjecture was recently proven for a brand-new class of networks that can be identified by characteristics of cut-set and source-sink paths. It's demonstrated the existence of a network that is not a member of this new class of networks and that allows routing to achieve the partition bound.