An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs Full article
| Conference |
The 12th International Conference on Analysis of Images, Social Networks and Texts, 17-19 Oct 2024 , Bishkek, Djal, Kyrgyz-Turkish Manas University |
||
|---|---|---|---|
| Source | Analysis of Images, Social Networks and Texts : Proceedings of the 12th International Conference, AIST 2024, Bishkek, Kyrgyzstan, October 17–19, 2024, Revised Selected Papers Compilation, Springer Nature. Switzerland.2025. 276 c. ISBN 978-3-031-88035-3. |
||
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||
| Output data | Year: 2025, Volume: 15419, Pages: 249–261 Pages count : 13 DOI: 10.1007/978-3-031-88036-0_15 | ||
| Tags | Bounded diameter spanning tree · Given diameter spanning tree · Approximation algorithm · Asymptotically optimal algorithm · Random inputs · Probabilistic analysis · Discrete distribution · Uniform distribution | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
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.
Cite:
Gimadi E.K.
, Tsidulko O.Y.
An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs
In compilation 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
In compilation 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
Dates:
| Published online: | Apr 15, 2025 |
| Published print: | May 17, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105003859311 |
| OpenAlex: | W4409407618 |
Citing:
Пока нет цитирований