No label defined (Q3745296)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3980505
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3980505

      Statements

      0 references
      0 references
      0 references
      1986
      0 references
      undirected spanning tree
      0 references
      undirected graph
      0 references
      polynomial solvable
      0 references
      NP-hard
      0 references
      multi-objective criteria
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references