Interval Spanning Trees Problem: Solvability and Computational Complexity
Галина Леонидовна Козина, V. A. Perepelitsa · 1994
The optimization Spanning Trees Problem on graphs with interval weights is presented. The interval function is defined as the sum of interval weights of feasible spanning tree edges. The relation order introduced into set of feasible solutions generates the Pareto set which is considered as the solution of the interval problem. The questions of solvability and computational complexity are investigated by applying the multicriterial approach.