title: ÐÐ»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð¿Ð¾Ð¸ÑÐºÐ° Ð´ÐµÑÐµÐ²Ð° Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð²ÐµÑÐ° Ñ Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð¸ÐµÐ¼ Ð·Ð°Ð´ÐµÑÐ¶ÐºÐ¸ Ð² Ð·Ð°Ð´Ð°ÑÐ°Ñ ÑÐµÐ»ÐµÐºÐ¾Ð¼Ð¼ÑÐ½Ð¸ÐºÐ°ÑÐ¸Ð¸
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: The algorithm to search for a minimum weight tree with a delay constraint in telecommunication tasks
Creators: name: Ð¡Ð¼Ð¸ÑÐ½Ð¾Ð²Ð°, ÐÐ°ÑÑÑ
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2022
Subjects: Ð½Ð°Ð¿ÑÐ°Ð²Ð»ÐµÐ½Ð½Ð¾Ðµ Ð´ÐµÑÐµÐ²Ð¾ Ð¨ÑÐµÐ¹Ð½ÐµÑÐ°
Ð¼Ð½Ð¾Ð³Ð¾Ð°Ð´ÑÐµÑÐ½Ð°Ñ Ð¼Ð°ÑÑÑÑÑÐ¸Ð·Ð°ÑÐ¸Ñ
Ð³ÑÐ°ÑÑ
Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð½Ð°Ñ Ð¾Ð¿ÑÐ¸Ð¼Ð¸Ð·Ð°ÑÐ¸Ñ
directed Steiner tree
multicast
graphs
constrained optimization
delay-bounded communication

description: Ð Ð´Ð°Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÐµ Ð¾Ð¿Ð¸ÑÐ°Ð½ Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ñ Ð½Ð°Ð¿ÑÐ°Ð²Ð»ÐµÐ½Ð½Ð¾Ð³Ð¾ Ð´ÐµÑÐµÐ²Ð° Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð¹ ÑÑÐ¾Ð¸Ð¼Ð¾ÑÑÐ¸ greedyFLAC. ÐÐ° ÐµÐ³Ð¾ Ð¾ÑÐ½Ð¾Ð²Ðµ ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐ°Ð½ Ð¼ÐµÑÐ¾Ð´ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ñ Ð´ÐµÑÐµÐ²Ð° Ð¨ÑÐµÐ¹Ð½ÐµÑÐ° Ñ Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð¸ÐµÐ¼. Ð Ð¿ÑÐµÐ´Ð»Ð¾Ð¶ÐµÐ½Ð½Ð¾Ð¼ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ðµ Ð¿ÑÐ¸Ð¼ÐµÐ½ÐµÐ½Ñ Ð¿Ð¾Ð´ÑÐ¾Ð´Ñ Ðº Ð²Ð²ÐµÐ´ÐµÐ½Ð¸Ñ Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð¸Ñ Ð½Ð° Ð·Ð°Ð´ÐµÑÐ¶ÐºÑ, Ð¸Ð·ÑÑÐµÐ½Ð½ÑÐµ Ð² ÑÐ¾Ð´Ðµ Ð°Ð½Ð°Ð»Ð¸Ð·Ð° ÑÑÑÐµÑÑÐ²ÑÑÑÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ñ Ð´ÐµÑÐµÐ²Ð° Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð³Ð¾ Ð²ÐµÑÐ° Ð² Ð¿ÑÐ¸Ð»Ð¾Ð¶ÐµÐ½Ð¸ÑÑ ÑÐµÐ»ÐµÐºÐ¾Ð¼Ð¼ÑÐ½Ð¸ÐºÐ°ÑÐ¸Ð¹, ÑÑÐ¸ÑÑÐ²Ð°ÑÑÐ¸Ñ Ð·Ð°Ð´ÐµÑÐ¶ÐºÑ Ð¿Ð¾ ÑÐµÑÐ¸. ÐÑÐ¾Ð²ÐµÐ´ÐµÐ½Ð¾ ÑÐµÑÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð¸Ðµ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ð½ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð², ÑÑÐ°Ð²Ð½ÐµÐ½Ð¸Ðµ Ð¸Ñ Ð¿Ð¾ ÑÐ¾ÑÐ½Ð¾ÑÑÐ¸ Ð¸ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ñ Ð°Ð½Ð°Ð»Ð¾Ð³Ð°Ð¼Ð¸. Ð ÑÐ¾Ð´Ðµ ÑÐºÑÐ¿ÐµÑÐ¸Ð¼ÐµÐ½ÑÐ¾Ð² Ð¿ÑÐµÐ´ÑÑÐ°Ð²Ð»ÐµÐ½Ð° Ð·Ð°Ð²Ð¸ÑÐ¸Ð¼Ð¾ÑÑÑ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ð¿ÑÐµÐ´Ð»Ð¾Ð¶ÐµÐ½Ð½Ð¾Ð³Ð¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° Ð¾Ñ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð° ÑÐµÑÐ¼Ð¸Ð½Ð°Ð»ÑÐ½ÑÑ Ð²ÐµÑÑÐ¸Ð½ Ð½Ð° Ð³ÑÐ°ÑÐµ Ð±Ð¾Ð»ÑÑÐ¾Ð³Ð¾ ÑÐ°Ð·Ð¼ÐµÑÐ°, Ð±Ð»Ð¸Ð·ÐºÐ¾Ð³Ð¾ Ðº ÑÐµÐ°Ð»ÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸ ÑÐµÐ»ÐµÐºÐ¾Ð¼Ð¼ÑÐ½Ð¸ÐºÐ°ÑÐ¸Ð¹ Ð³Ð¾ÑÐ¾Ð´Ð°. Ð ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ Ð¿ÑÐ¾Ð²ÐµÐ´ÐµÐ½Ð½Ð¾Ð³Ð¾ Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ñ ÑÐ´ÐµÐ»Ð°Ð½Ñ Ð²ÑÐ²Ð¾Ð´Ñ Ð¾ ÑÐ¾Ð¼, ÑÑÐ¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ greedyFLAC Ð´Ð°ÐµÑ Ð»ÑÑÑÐµÐµ Ð¿ÑÐ¸Ð±Ð»Ð¸Ð¶ÐµÐ½Ð¸Ðµ Ð´ÐµÑÐµÐ²Ð° Ð¨ÑÐµÐ¹Ð½ÐµÑÐ°, Ð¿ÑÐ¸ ÑÑÐ¾Ð¼ ÑÑÐµÐ±ÑÑ Ð±Ð¾Ð»ÑÑÐ¸Ñ Ð²ÑÐµÐ¼ÐµÐ½Ð½ÑÑ Ð·Ð°ÑÑÐ°Ñ, Ð¸ ÑÑÐ¾ Ð¿ÑÐµÐ´Ð»Ð¾Ð¶ÐµÐ½Ð½ÑÐ¹ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð½Ð° Ð½ÐµÐºÐ¾ÑÐ¾ÑÐ¾Ð¼ Ð¿Ð¾Ð´Ð¼Ð½Ð¾Ð¶ÐµÑÑÐ²Ðµ Ð³ÑÐ°ÑÐ¾Ð² Ð½Ð°ÑÐ¾Ð´Ð¸Ñ Ð´ÐµÑÐµÐ²Ð¾ Ð¼ÐµÐ½ÑÑÐµÐ¹ ÑÑÐ¾Ð¸Ð¼Ð¾ÑÑÐ¸, ÑÐµÐ¼ ÐµÐ³Ð¾ Ð°Ð½Ð°Ð»Ð¾Ð³, Ð¿ÑÐ¸ ÑÑÐ¾Ð¼ ÑÐ°ÐºÐ¶Ðµ ÑÐ²Ð»ÑÐµÑÑÑ Ð±Ð¾Ð»ÐµÐµ ÑÑÐµÐ±Ð¾Ð²Ð°ÑÐµÐ»ÑÐ½ÑÐ¼ Ð¿Ð¾ Ð²ÑÑÐ¸ÑÐ»Ð¸ÑÐµÐ»ÑÐ½ÑÐ¼ ÑÐµÑÑÑÑÐ°Ð¼.
description: In this work we describe and implement an algorithm greedyFLAC for constructing a directional minimum cost tree. On its basis, a method for constructing a Steiner tree with constraint is developed. The proposed algorithm applies the approaches for introducing a delay constraint studied during the analysis of existing minimum cost tree algorithms in telecommunication applications that consider the network delay. We tested the implemented algorithms and compared them in terms of accuracy and performance with their counterparts. During the experiments we presented the dependence of the performance on the number of terminal nodes of the proposed algorithm in a large-sized graph close to the real city telecommunications network. As a result of the study, it is concluded that the greedyFLAC algorithm gives a better approximation of the Steiner tree, though requiring more time, and that the proposed algorithm on subset of graphs finds a tree of less cost than its counterpart, while also being more computationally demanding.