Combining Linear and Non-Linear Objectives in Spanning Tree Problems |
| |
Authors: | Mauro Dell'Amico Francesco Maffioli |
| |
Institution: | (1) DISMI, Università di Modena e Reggio Emilia, viala Allegri 15, 42100 Reggio Emilia, Italy;(2) DEI, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy |
| |
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. |
| |
Keywords: | computational complexity spanning tree cumulative function |
本文献已被 SpringerLink 等数据库收录! |
|