An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs Научная публикация
Конференция |
The 12th International Conference on Analysis of Images, Social Networks and Texts, 17-19 окт. 2024 , Bishkek, Djal, Kyrgyz-Turkish Manas University |
||
---|---|---|---|
Сборник | Analysis of Images, Social Networks and Texts : Proceedings of the 12th International Conference, AIST 2024, Bishkek, Kyrgyzstan, October 17–19, 2024, Revised Selected Papers Сборник, Springer Nature. Switzerland.2025. 276 c. ISBN 978-3-031-88035-3. |
||
Журнал |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||
Вых. Данные | Год: 2025, Том: 15419, Страницы: 249–261 Страниц : 13 DOI: 10.1007/978-3-031-88036-0_15 | ||
Ключевые слова | Bounded diameter spanning tree · Given diameter spanning tree · Approximation algorithm · Asymptotically optimal algorithm · Random inputs · Probabilistic analysis · Discrete distribution · Uniform distribution | ||
Авторы |
|
||
Организации |
|
Информация о финансировании (1)
1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
Реферат:
We consider the problem of finding minimum-weight spanning tree with a diameter, which is either at most or equal to a given bound d, in a complete edge-weighted undirected graph. We propose a new simple polynomial-time approximation algorithm for this problem and provide probabilistic analysis of the algorithm on random inputs in which the weights of edges are i.i.d. random variables with either uniform continuous distribution on [an,bn] or uniform discrete distribution on segment [an,bn] ∩ N, 0 < an ≤ bn. We prove conditions on an and bn under which the algorithm is asymptotically optimal on these classes of random inputs. The main advantage of the new algorithm is that its asymptotic optimality conditions do not depend on the value of diameter bound d, in contrast to the previously known results.
Библиографическая ссылка:
Gimadi E.K.
, Tsidulko O.Y.
An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs
В сборнике Analysis of Images, Social Networks and Texts : Proceedings of the 12th International Conference, AIST 2024, Bishkek, Kyrgyzstan, October 17–19, 2024, Revised Selected Papers. – Springer Nature., 2025. – C.249–261. – ISBN 978-3-031-88035-3. DOI: 10.1007/978-3-031-88036-0_15 Scopus OpenAlex
An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs
В сборнике Analysis of Images, Social Networks and Texts : Proceedings of the 12th International Conference, AIST 2024, Bishkek, Kyrgyzstan, October 17–19, 2024, Revised Selected Papers. – Springer Nature., 2025. – C.249–261. – ISBN 978-3-031-88035-3. DOI: 10.1007/978-3-031-88036-0_15 Scopus OpenAlex
Даты:
Опубликована online: | 15 апр. 2025 г. |
Опубликована в печати: | 17 мая 2025 г. |
Идентификаторы БД:
Scopus: | 2-s2.0-105003859311 |
OpenAlex: | W4409407618 |
Цитирование в БД:
Пока нет цитирований