scientific article; zbMATH DE number 3980505

From MaRDI portal
Publication:3745296





[For the entire collection see Zbl 0592.00028.] Optimum undirected spanning tree problems may be formulated as follows. Let \(G=(V,E)\) be an undirected graph, s be a mapping which associates with each spanning tree of G a system s(T) of edge sets in T, and f be an integer valued function defined on subsets of the edge set E of G. Find a spanning tree \(T^*\) which optimizes \(g(T)=\oplus \{f(S)|\) \(S\in s(T)\}\) where the operator \(\oplus\) stands for min, max or \(\sum.\) A survey is given on the complexity status of these type of problems with respect to several evaluation functions g identifying the borderline between polynomial solvable and NP-hard problems. Also problems with multi-objective criteria are investigated.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3745296)