|
|||||
|
|
On the Biobjective Adjacent Only Quadratic Spanning Tree Problem |
|
| Affiliation: | 1. Graz University of Technology, Institute of Discrete Mathematics, Steyrergasse 30, 8010 Graz, Austria;2. Institute for Basic Science (IBS), Discrete Mathematics Group, 55, Expo-ro, Yuseong-gu, Daejeon, 34126 Republic of Korea;3. Universität Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany;4. Alfréd Rényi Institute of Mathematics, Set theory and general topology research division, 13-15 Reáltanoda St., Budapest, Hungary |
| Abstract: | The adjacent only quadratic minimum spanning tree problem is an NP-hard version of the minimum spanning tree where the costs of interaction effects between every pair of adjacent edges are included in the objective function. This paper addresses the biobjective version of this problem. A Pareto local search algorithm is proposed. The algorithm is applied to a set of 108 benchmark instances. The results are compared to the optimal Pareto front generated by a branch and bound algorithm, which is a multiobjective adaptation of a well known algorithm for the mono-objective case. |
| Keywords: | Multiobjective Optimization Quadratic Minimum Spanning Tree Pareto Local Search Branch and Bound |
| 本文献已被 ScienceDirect 等数据库收录！ | |