Models and Complexity of Problems of Design and Reconstruction of Telecommunication and Transport Systems

This article considers network synthesis problems arising in the design and exploitation of telecommunication and transportation systems. A formalization of network synthesis problems on graphs is proposed in which constraints on cut capacities are given and possibilities of failing some network components are taken into account. Approaches to the solution and analysis of the complexity of the considered problems are described.