Interval Spanning Trees Problem: Solvability and Computational Complexity

Галина Леонидовна Козина, V. A. Perepelitsa

1994 · 19 citations · 2 references

Concepts

Abstract

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.

References

2