Article ID: | iaor20001009 |
Country: | Netherlands |
Volume: | 111 |
Issue: | 3 |
Start Page Number: | 617 |
End Page Number: | 628 |
Publication Date: | Dec 1998 |
Journal: | European Journal of Operational Research |
Authors: | Ramos R.M., Sicilia J., Alonso S., Gonzlez C. |
Keywords: | networks |
This paper studies the problem of finding the set of optimal spanning trees of a connected graph, considering two cost functions defined on the set of edges. This problem is NP-hard and the solution is described through an algorithm that builds the family of efficient trees. This algorithm needs two procedures that solve the following uniobjective problems: the construction of all the spanning trees of a connected graph and the construction of the whole set of minimum cost spanning trees. The computational results obtained are shown.