ISSN:
1573-2886
Keywords:
computational complexity
;
spanning tree
;
cumulative function
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions. We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009854922371
Permalink