The communication network topology problem is studied with no edge costs and node costs depending on the node degree and capacity. If cost depends on the degree only, the optimal network is shown to be the tree T of known cost. If capacity only matters, a two-layered network N is optimal where secondary nodes form a complete graph. When both degree and capacity matter, LB and UB are constructed using costs of T and N networks. A branch-and-bound procedure is designed. The local search heuristics is suggested and tested on a collection of random networks.
