Hierarchical topological network design

We present a hierarchical solution method to approximately solve the topological network design problem: given positive integers (n,d,Δ), minimize the number of arcs required to interconnect n nodes, so that the network diameter does not exceed d, the maximum node degree does not exceed Δ, and the network is single node survivable. The method uses dynamic programming to piece together small networks to create larger networks. The method was used to plan two high-speed packet networks at AT&T.