Combining linear and non-linear objectives in spanning tree problems

被引：5
|
作者：
Dell'Amico, M
Maffioli, F
机构：
[1] Univ Modena & Reggio Emilia, DISMI, I-42100 Reggio Emilia, Italy
[2] Politecn Milan, DEI, I-20133 Milan, Italy
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2000年 / 4卷 / 02期
关键词：
computational complexity; spanning tree; cumulative function;
D O I：
10.1023/A:1009854922371
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
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.
引用
收藏
页码：253 / 269
页数：17
相关论文
共 50 条
12345