Network decomposition for the optimization of connection structures

Publisher Website
Google Scholar
Abstract
In many practical situations, connection structures have to be laid out in an environment with a strong inner structure. This article presents a new general mathematical formulation of cor responding design problems in which the layout possibilities are represented by a network. Because in practice such networks are often very large and sparse, there is great interest in the utilization of decomposition techniques for the optimization of connection structures. New decomposition methods for the determination of optimal paths without interference (independent decom position), of k node‐disjoint paths with minimal total costs and of optimal Steiner trees are presented. The new methods are compared with other techniques under different aspects of practical importance.