Enumeration of Pareto optimal multi-criteria spanning trees – a proof of the incorrectness of Zhou and Gens proposed algorithm》.pdf

European Journal of Operational Research 143 (2002) 543–547 /locate/dsw Discrete Optimization Enumeration of Pareto optimal multi-criteria spanning trees – a proof of the incorrectness of Zhou and Gen’s proposed algorithm Joshua D. Knowles , David W. Corne Department of Computer Science, University of Reading, Reading, UK Received 16 January 2001; accepted 25 September 2001 Abstract The minimum spanning tree (MST) problem is a well-known optimization problem of major significance in oper- ational research. In the multi-criteria MST (mc-MST) problem, the scalar edge weights of the MST problem are re- placed by vectors, and the aim is to find the complete set of Pareto optimal minimum-weight spanning trees. This problem is NP-hard and so approximate methods must be used if one is to tackle it efficiently. In an article previously published in this journal, a genetic algorithm (GA) was put forward for the mc-MST. To evaluate the GA, the solution sets generated by it were compared with solution sets from a proposed (exponential time) algorithm for enumerating all Pareto optimal spanning trees. However, the proposed enumeration algorithm that was used is not correct for two reasons: (1) It does not guarantee that all Pareto optimal minimum-weight spanning trees are returned. (2) It does not guarantee that those trees that are returned are Pareto optimal. In this short paper we prove these two theorems. 2002 Elsevier Science B.V. All rights reserved. Keywords: Combinatorial optimization; Minimum spanning tree; Graph theory; Multiple-criteria optimizati