Premium
Network decomposition for the optimization of connection structures
Author(s) -
Iwainsky Alfred,
Canuto Enrico,
Taraszow Oleg,
Villa Agostino
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160209
Subject(s) - connection (principal bundle) , disjoint sets , decomposition , mathematical optimization , computer science , node (physics) , position (finance) , interference (communication) , decomposition method (queueing theory) , mathematics , theoretical computer science , algorithm , discrete mathematics , computer network , engineering , ecology , channel (broadcasting) , geometry , structural engineering , finance , economics , biology
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.