Abstract. We address network synthesis problems arising in the design and exploitation of telecommunication and transportation systems. We focus on the formulations of the network design problems on graphs with bounded capacities of cuts and connectivity requirements after some network components fail. We discuss the approaches to problem solutions and analyze their run times.
Keywords: design and reliability of a network, minimum cut, submodular function, cut function, optimal topology.
Шарифов Фирдовси Ахун-оглы,
доктор физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: f-sharifov@yandex.ru.
Гуляницкий Леонид Федорович, доктор техн. наук, заведующий отделом Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: leonhul.icyb@gmail.com.