Relations,models and a memetic approach for three degree-dependent spanning tree problems |
| |
Authors: | C. Cerrone R. Cerulli A. Raiconi |
| |
Affiliation: | 1. Department of Computer Science, University of Salerno, Via Giovanni Paolo II n. 132, 84084 Fisciano (SA), Italy;2. Department of Mathematics, University of Salerno, Via Giovanni Paolo II n. 132, 84084 Fisciano (SA), Italy |
| |
Abstract: | In this paper we take into account three different spanning tree problems with degree-dependent objective functions. The main application of these problems is in the field of optical network design. In particular, we propose the classical Minimum Leaves Spanning Tree problem as a relevant problem in this field and show its relations with the Minimum Branch Vertices and the Minimum Degree Sum Problems. We present a unified memetic algorithm for the three problems and show its effectiveness on a wide range of test instances. |
| |
Keywords: | Combinatorial optimization Memetic algorithms Spanning trees Optical networks |
本文献已被 ScienceDirect 等数据库收录! |
|