Abstract—The quadratic minimum spanning tree problem is to find a spanning tree on a graph that minimizes a quadratic objective function of the edge weights. In this paper, the quadratic minimum spanning tree problem is concerned on the graph with edge weights being assumed as uncertain variables. The notion of the uncertain quadratic -minimum spanning tree is introduced by using the uncertain chance constraints. It is shown that the problem of finding an uncertain quadratic α-minimum spanning tree can be handled in the framework of the deterministic quadratic minimum spanning tree problem requiring no particular solving methods.

Index Terms—Quadratic minimum spanning tree, uncertainty theory, network optimization, chance-constrained programming

Cite: Jian Zhou, Xing He, and Ke Wang, "Uncertain Quadratic Minimum Spanning Tree Problem," Journal of Communications, vol. 9, no. 5, pp. 385-390, 2014. Doi: 10.12720/jcm.9.5.385-390