title: ÐÐ°Ð´Ð°ÑÐ° Ð¾ Ð¼Ð¸Ð½Ð¸Ð¼Ð°Ð»ÑÐ½Ð¾Ð¼ Ð´ÐµÑÐµÐ²Ðµ Ð² ÑÐµÐ»ÐµÐºÐ¾Ð¼Ð¼ÑÐ½Ð¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½ÑÑ ÑÐµÑÑÑ
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Steiner problem in telecommunication networks
Creators: name: ÐÐ°Ð¼Ð°ÑÐºÐ¸Ð½ÑÐºÐ¸Ð¹, ÐÐ¾Ð½ÑÑÐ°Ð½ÑÐ¸Ð½
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2021
Subjects: Ð·Ð°Ð´Ð°ÑÐ° ÑÑÐµÐ¹Ð½ÐµÑÐ°
Ð³ÑÐ°ÑÑ
Ð¼Ð½Ð¾Ð³Ð¾Ð¿Ð¾ÑÐ¾ÑÐ½Ð¾ÑÑÑ
ÑÐµÐ»ÐµÐºÐ¾Ð¼Ð¼ÑÐ½Ð¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½ÑÐµ ÑÐµÑÐ¸
ÑÐ¾ÑÐ½ÑÐµ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ñ
steiner problem
multithreading
telecommunication networks
exact algorithms

description: ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ñ ÑÐ¾ÑÐ½ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² ÑÐµÑÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¨ÑÐµÐ¹Ð½ÐµÑÐ° Ð½Ð° Ð³ÑÐ°ÑÐ°Ñ. Ð¦ÐµÐ»ÑÑ ÑÐ°Ð±Ð¾ÑÑ ÑÐ²Ð»ÑÐµÑÑÑ ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ Ð¿Ð°ÑÐ°Ð»Â­ Ð»ÐµÐ»ÑÐ½Ð¾Ð³Ð¾ ÑÐ¾ÑÐ½Ð¾Ð³Ð¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÑÐµÑÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¨ÑÐµÐ¹Ð½ÐµÑÐ° Ð½Ð° Ð½ÐµÐ¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÑ Ð¸ Ð¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÑ Ð³ÑÐ°ÑÐ°Ñ. Ð ÑÐ¾Ð´Ðµ ÑÐ°Ð±Ð¾ÑÑ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ñ Ð¸ ÑÐµÐ°Ð»Ð¸Ð·Ð¾Ð²Ð°Ð½Ñ Ð´Ð²Ð° Ð°Ð»Ð³Ð¾Â­ ÑÐ¸ÑÐ¼Ð° ÑÐµÑÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð½Ð° Ð½ÐµÐ¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÑ Ð³ÑÐ°ÑÐ°Ñ Ð¸ Ð´Ð²Ð° Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÑÐµÑÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð½Ð° Ð¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÑ Ð³ÑÐ°ÑÐ°Ñ. ÐÐ¾Ð»ÑÑÐµÐ½Ð¾, ÑÑÐ¾ Ð·Ð°Ð´Ð°ÑÐ¸ Ñ ÑÐ¸ÑÐ»Ð¾Ð¼ Ð²ÐµÑÑÐ¸Ð½ Ð´Ð¾ 20000 Ð¸ ÑÐ¸ÑÐ»Ð¾Ð¼ ÑÐµÑÐ¼Ð¸Ð½Ð°Ð»Ð¾Ð² Ð´Ð¾ 9 Ð¼Ð¾Ð³ÑÑ Ð±ÑÑÑ ÑÐµÑÐµÐ½Ñ Ð±ÑÑÑÑÐµÐµ, ÑÐµÐ¼ Ð·Ð° 20 ÑÐµÐºÑÐ½Ð´. ÐÑÐ¾Ð¸Ð·Ð²ÐµÐ´ÐµÐ½Ð° Ð¾ÑÐµÐ½ÐºÐ° Ð·Ð°Ð²Ð¸ÑÐ¸Ð¼Ð¾ÑÑÐ¸ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð½ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² Ð¾Ñ Ð¿Ð°ÑÐ°Ð¼ÐµÑÑÐ¾Ð² Ð·Ð°Ð´Ð°ÑÐ¸ Ð¨ÑÐµÐ¹Ð½ÐµÑÐ° â ÑÐ¸ÑÐ»Ð° Ð²ÐµÑÑÐ¸Ð½, ÑÐ¸ÑÐ»Ð° ÑÑÐ±ÐµÑ, ÑÐ¸ÑÐ»Ð° ÑÐµÑÐ¼Ð¸Ð½Ð°Â­ Ð»Ð¾Ð². Ð¢Ð°ÐºÐ¶Ðµ Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð° Ð·Ð°Ð²Ð¸ÑÐ¸Ð¼Ð¾ÑÑÑ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ð¾Ñ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð° Ð¿Ð¾ÑÐ¾ÐºÐ¾Ð². Ð¢ÐµÐ¾ÑÐµÑÐ¸ÑÐµÑÐºÐ°Ñ Ð¾ÑÐµÐ½ÐºÐ° Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð½ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð² ÑÐ¾Ð²Ð¿Ð°Ð»Ð° Ñ ÑÐ°ÐºÑÐ¸ÑÐµÑÐºÐ¾Ð¹. ÐÐ°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð°Ñ Ð²ÐµÑÑÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÐÑÐµÐ¹ÑÑÑÐ°, ÐÐ°Ð³Ð½ÐµÑÐ° Ð´Ð°Ð»Ð° Ð¿ÑÐ¸ÑÐ¾ÑÑ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾ÑÑÐ¸ Ð² 3,5 ÑÐ°Ð·Ð°, Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð°Ñ Ð²ÐµÑÑÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° Ð­ÑÐ¸ÐºÑÐ¾Ð½Ð°, ÐÐ¾Ð½Ð¼Ñ, ÐÐµÐ¹Ð½Ð¾ÑÑÐ° â Ð² 3,2 ÑÐ°Ð·Ð°. ÐÐ½Ð°Ð»Ð¾Ð³Ð¸ÑÐ½ÑÐµ Ð·Ð½Ð°ÑÐµÐ½Ð¸Ñ Ð±ÑÐ»Ð¸ Ð¿Ð¾Ð»ÑÑÐµÐ½Ñ Ð´Ð»Ñ Ð¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½ÑÑ Ð²ÐµÑÑÐ¸Ð¹ ÑÐ¾Ð¾ÑÐ²ÐµÑÑÑÐ²ÑÑÑÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð². ÐÐ¾Ð»ÑÑÐµÐ½Ð½ÑÐµ ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÑ Ð¿Ð¾Ð·Ð²Ð¾Ð»ÑÑÑ ÑÐ´ÐµÐ»Ð°ÑÑ Ð²ÑÐ²Ð¾Ð´ Ð¾Ð± ÑÑÑÐµÐºÑÐ¸Ð²Ð½Ð¾ÑÑÐ¸ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð½Ð¾Ð¹ Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð¾Ð¹ ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð². ÐÐ»Â­ Ð³Ð¾ÑÐ¸ÑÐ¼ ÐÑÐµÐ¹ÑÑÑÐ°, ÐÐ°Ð³Ð½ÐµÑÐ° Ð±ÑÐ» ÑÑÐ¿ÐµÑÐ½Ð¾ Ð¿ÑÐ¸Ð¼ÐµÐ½ÑÐ½ Ð² ÑÐ°Ð¼ÐºÐ°Ñ ÑÐ¾Ð²Ð¼ÐµÑÑÐ½Ð¾Ð³Ð¾ Ð¿ÑÐ¾ÐµÐºÑÐ° Ð¡ÐÐ±ÐÐ£ Ð¸ Huawei.
description: The present work is devoted to the research of exact algorithms for Steiner problem in graphs. The aim is to develop and to implement parallel exact algorithms for Steiner problem in undirected and directed graphs. Two algorithms for the problem in undirected graphs and two algorithms for the problem in directed graphs have been implemented. The research has shown that problems having up to 20000 vertives and up to 9 terminals can be solved in 20 seconds. Performance measurements have been done. It has been checked that theoretical performance fits actual performance. It has been shown that parallel version of Dreyfus, Wagner algorithm increased performance up to 3.5 times, parallel version of Erickson, Monma, Veinott algorithm â up to 3.2 times. The equal results have been received for directed versions of mentioned algorithms. Results allow us to make conclusion about efficiency of parallel implementations. Dreyfus, Wagner algorithm has been successully applied to the R&amp;D project of SPbPU and Huawei.