Technical Report Number
A general framework for specifying communication network design problems is given. We analyze the computational complexity of several specific problems within this framework. For fixed multirate traffic requirements, we prove that a particular network analysis problem is NP-complete, although several related network design problems are either efficiently solvable or have good approximation algorithms. For the case when we wish the network to operate without blocking any connection requests, we give efficient algorithms for dimensioning the link capacities of the network.
Fingerhut, J. Andrew, "Designing Communication Networks with Fixed or Nonblocking Traffic Requirements" Report Number: WUCS-91-55 (1992). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7B56H2F