ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 5, 49, 90 Winzer, Olga, Zaporozhye State University, Ukraine Complexity of vector spanning trees problems with topological criteria Let G = (V, E) is n - vertices 2 - weighted graph, X = {x} is its spanning tree; X = X(G) = {x} is the set of all spanning trees of graph G. The vector objective function (VOF) F (x) = (F_{1}(x), F_{2}(x)), F_{ν}(x) → min, ν = 1, 2 is determined on X. VOF determines Pareto set X^{∼} and a complete set of alternative (CSA) X^{0}, X^{0} ⊆X^{∼}⊆ X. CSA X^{0} is unknown solution of problem. Finding CSA has exponential computing complexity in case when criteria F_{ν}(x), ν = 1, 2 represents sum of weights of edges e ∈ E_{x}. We consider such problems: VOF contains if only one topological criterion: diameter of a tree or its degree. Then 2 criteria spanning trees problem is NP - hard. Reference: Emelichev V. A. and Perepelitsa V. A., Multiobjective Problem on the Spanning Trees of Graf, Soviet Math. Dokl. , Vol. 37 (1988) N1, 114-117.