Extensions of the minimum labelling spanning tree problem

• Autorzy: Cerulli R. , Fink A. , Gentili M. , Voss S.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose some extensions of the minimum labelling spanning tree problem. The main focus is on the minimum labelling Steiner tree problem: given a graph G with a color (label) assigned to each edge, and a subset Q of the nodes of G (basic vertices), we look for a connected subgraph of G with the minimum number of different colors covering all the basic vertices. The problem has several applications in telecommunication networks, electric networks, multimodal transportation networks, among others, where one aims to ensure connectivity by means of homogeneous connections. Numerical results for several metaheuristics to solve the problem are presented.

Słowa kluczowe

EN

network design; metaheuristics; spanning trees; labelling trees; Steiner tree problem

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2006
• Tom: nr 4
• Strony: 39--45
• Opis fizyczny: Bibliogr. 23 poz., tab.

Twórcy

autor

Cerulli R.

autor

Fink A.

autor

Gentili M.

autor

Voss S.

• Department of Mathematics and Computer Science, University of Salerno, Via Ponte Don Melillo, 84084, Fisciano (Salerno), Italy,

Bibliografia

• [1] R. Battiti, “Reactive search: toward self-tuning heuristics”, in Modern Heuristic Search Methods, V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, and G. D. Smith, Eds. Chichester: Wiley, 1996, pp. 61–83.
• [2] H. Broersma and X. Li, “Spanning trees with many or few colors in edge-colored graphs”, Discus. Math. Graph Theory, vol. 17, pp. 259–269, 1997.
• [3] T. Br ¨uggemann, J. Monnot, and G. J. Woeginger, “Local search for the minimum label spanning tree problem with bounded color classes”, Oper. Res. Lett., vol. 31, pp. 195–201, 2003.
• [4] R. Cerulli, A. Fink, M. Gentili, and S. Voß, “Applications of the pilot method and VNS to hard modifications of the minimum spanning tree problem”, in Mini Euro Conf. VNS, Tenerife, Spain, 2005.
• [5] R. Cerulli, A. Fink, M. Gentili, and S. Voß, “Metaheuristics comparison for the minimum labelling spanning tree problem”, in The Next Wave on Computing, Optimization, and Decision Technologies, B. L. Golden, S. Raghavan, and E. A. Wasil, Eds. New York: Springer, 2005, pp. 93–106.
• [6] R.-S. Chang and S.-J. Leu, “The minimum labeling spanning trees”, Inform. Proces. Lett., vol. 63, pp. 277–282, 1997.
• [7] C. W. Duin and S. Voß, “The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs”, Networks, vol. 34, pp. 181–191, 1999.
• [8] A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by metaheuristics”, in Computing Tools for Modeling, Optimization and Simulation, M. Laguna and J. L. Gonz´alez Velarde, Eds. Boston: Kluwer, 2000, pp. 91–113.
• [9] F. Glover and M. Laguna, Tabu Search. Boston: Kluwer, 1997.
• [10] F. K. Hwang and D. S. Richards, “Steiner tree problems”, Networks, vol. 22, pp. 55–89, 1992.
• [11] F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem. Amsterdam: North-Holland, 1992.
• [12] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by simulated annealing: an experimental evaluation”, Part I, “Graph partitioning”, Oper. Res., vol. 37, pp. 865–892, 1989.
• [13] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, pp. 671–680, 1983.
• [14] S. O. Krumke and H.-C. Wirth, “On the minimum label spanning tree problem”, Inform. Proces. Lett., vol. 66, pp. 81–85, 1998.
• [15] N. Mladenović and P. Hansen, “Variable neighbourhood search”, Comput. Oper. Res., vol. 24, pp. 1097–1100, 1997.
• [16] S. Voß, “Modern heuristic search methods for the Steiner tree problem in graphs”, in Advances in Steiner Trees, D.-Z. Du, J. M. Smith, and J. H. Rubinstein, Eds. Boston: Kluwer, 2000, pp. 283–323.
• [17] S. Voß, “Steiner tree problems in telecommunications”, in Handbook of Optimization in Telecommunications, M. Resende and P. M. Pardalos, Eds. New York: Springer, 2006, pp. 459–492.
• [18] S. Voß, A. Fink, and C. Duin, “Looking ahead with the pilot method”, Ann. Oper. Res., vol. 136, pp. 285–302, 2004.
• [19] Y.Wan, G. Chen, and Y. Xu, “A note on the minimum label spanning tree”, Inform. Proces. Lett., vol. 84, pp. 99–101, 2002.
• [20] P. Winter, “Steiner problem in networks: a survey”, Networks, vol. 17, pp. 129–167, 1987.
• [21] Y. Xiong, B. Golden, and E. Wasil, “A one-parameter genetic algorithm for the minimum labeling spanning tree problem”. Tech. Rep., University of Maryland, 2003.
• [22] Y. Xiong, B. Golden, and E. Wasil, “Improved metaheuristics for the minimum labeling spanning tree problem”. Tech. Rep., University of Maryland, 2005 (also in Metaheur. Int. Conf., Vienna, Austria, 2005).
• [23] Y. Xiong, B. Golden, and E. Wasil, “Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem”, Oper. Res. Lett., vol. 33, pp. 77–80, 2005.