The probabilistic minimum spanning tree problem
Author:
Abstract
In this paper we consider a natural probabilistic variation of the classical minimum spanning tree problem (MST), which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed‐form expression for the expected length of a given spanning tree. Based on these expressions, we prove that the problem is NP‐complete. We further examine some interesting combinatorial properties of the problem, establish the relation of the PMST with the MST and the network design problem, and examine some cases where the problem is solvable in polynomial time. We finally characterize the asymptotic behavior of reoptimization strategies, in which we find the MST or the Steiner tree, respectively, among the points that are present on a particular instance, and the PMST, in the case in which points are randomly distributed in the Euclidean plane and in the case in which the costs of the ares are randomly distributed. In both cases the PMST is within constant factors from both strategies.Keywords
This publication has 7 references indexed in Scilit:
- Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted EdgesThe Annals of Probability, 1988
- On Frieze's χ(3) limit for lengths of minimal spanning treesDiscrete Applied Mathematics, 1987
- Probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean SpaceStochastic Processes and their Applications, 1987
- On the value of a random minimum spanning tree problemDiscrete Applied Mathematics, 1985
- Subadditive Euclidean Functionals and Nonlinear Growth in Geometric ProbabilityThe Annals of Probability, 1981
- The complexity of the network design problemNetworks, 1978
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959