Performance comparison of the AS and GTSalgorithms for weighted maximum leaf spanning tree problem

• Autorzy: Czaderna P. , Wala K.
• Konferencja: Evolutionary Computation and Global Optimization (10; Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna; 11-13.06.2007; Będlewo, Poland)
• Języki publikacji: EN

Abstrakty

EN

In the paper the combinatorial model of the weighted maximum leaf spanning tree problem of simple graph is presented. We give a detailed description of three procedures of the neighbour trees generation to the basis one which are exploited during the course of tree improving process realized by the classical simulated annealing and genetic local search algorithm. Numerical results of improving processes for randomly generated praphs are included.

Słowa kluczowe

EN

algorithms method; combinatorial method

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2007
• Tom: z. 160
• Strony: 43--50
• Opis fizyczny: Bibliogr. 8 poz., schem.

Twórcy

autor

Czaderna P.

autor

Wala K.

• Academy of Computer Science and Management Bielsko-Biała Poland,

Bibliografia

• [1] Ahuja R.K., Orlin J.B., Sharma D., Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem. Working Paper, University of Florida, 2001. Submitted for publication.
• [2] Czaderna P., Wala K., Simulated annealing in maximization of the leafs weight of spanning tree (in Polish). Automatics No 143, The Silesian University of Technology Press, Gliwice 2006.
• [3] Fernandes L.M., Gouveia L., Minimal spanning trees with a constraint on the number of leaves. European J. of Operational Research, Vol. 104, pp. 250-261, 1998.
• [4] Fujie T., An exact algorithm for the maximum leaf spanning tree problem. Computer & Operations Research 30, 1931-1944, 2003.
• [5] Kirkpatrick S., Gellat P.D., Vecchi M.P., Optimization by simulated annealing. Science 220 (1983), 671-680.
• [6] Loryś K., Zwoźniak G., Approximation algorithms for Maximum-leaf Spanning Tree for cubic graphs. Mohring R. and Raman R. (Eds), ESA 2002, LNCS2461, pp. 686-698, Springer-Verlag 2002.
• [7] Lu H., Ravi R., The power of local optimization: Approximation algorithms for Maximum-leaf Spanning Tree - Proceedings of the Thirtieth Annual Allerton Conference on Communication, Control and Computing, pp. 533-542, 1992.
• [8] Lu H., Ravi R., A near-linear-time approximation algorithms for Maximum-leaf Spanning Tree. Journal of Algorithms, Vol. 29, No 1, pp. 132-141, 1995.