On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
- 1 July 2023
- journal article
- research article
- Published by Pleiades Publishing Ltd in Automation and Remote Control
- Vol. 84 (7) , 772-787
Abstract
We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity \(\mathcal{O}\)(n2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.
Keywords
This publication has 9 references indexed in Scilit:
- Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded belowJournal of Applied and Industrial Mathematics, 2015
- On the Length of a Random Minimum Spanning TreeCombinatorics, Probability and Computing, 2015
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networksCombinatorica, 2012
- An asymptotically exact algorithm for one modification of planar three-index assignment problemJournal of Applied and Industrial Mathematics, 2007
- Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks2005
- Multicasting in a linear lightwave network2002
- Probability inequalities for sums of independent random variables1995
- A tree-based algorithm for distributed mutual exclusionACM Transactions on Computer Systems, 1989
- On the value of a random minimum spanning tree problemDiscrete Applied Mathematics, 1985