search query: @indexterm Graphs / total: 86
reference: 6 / 86
Author: | Knowles, J. D. Corne, D. W. |
Title: | Enumeration of Pareto optimal multi-criteria spanning trees - a proof of the incorrectness of Zhou and Gen's proposed algorithm |
Journal: | European Journal of Operational Research
2002 : DEC, VOL. 143:3, p. 543-547 |
Index terms: | OPTIMIZATION GRAPHS ALGORITHMS PARETO LAW |
Language: | eng |
Abstract: | The minimum spanning tree (MST) problem is a well- known optimization problem of major significance in operational research. In the multi-criteria MST (mc-MST) problem, the scalar edge weights of the MST problem are replaced 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. |
SCIMA