The Minimum Labeling Spanning Tree and Related Problems
Resumo
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph in which each edge has one label associated, by using a minimum number of labels. It is an NP-hard problem that has attracted substantial research attention in recent years. In its turn, the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of the MLSTP that allows the situation in which multiple labels can be assigned to an edge. Both problems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. The thesis addresses several connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in the work can be classified between theoretical and practical. On the theoretical side, it has introduced new useful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well as a polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics and new mathematical formulations and branch-and-cut algorithms. The new approaches introduced have achieved the best results for both heuristic and exact methods in comparison with the state-of-the-art.
Referências
Cerrone, C., Cerulli, R. e Golden, B. (2017), Carousel greedy: a generalized greedy algorithm with applications in optimization. Computers & Operations Research, v. 85, p. 97–112
Cerulli, R., Fink, A., Gentili, M. e Raiconi, A. (2014), The k-labeled spanning forest problem. Procedia - Social and Behavioral Sciences, v. 108, p. 153–163.
Chwatal, A. M. e Raidl, G. R. (2011), Solving the minimum label spanning tree problem by mathematical programming techniques. Adv. Operations Research, v. 2011
Consoli, S., Mladenovi´c, N. e Moreno P´erez, J. (2015), Solving the minimum labelling spanning tree problem by intelligent optimization. Appl. Soft Comput., v. 28, n. C, p. 440–452
Ismkhan, H. (2017), Effective three-phase evolutionary algorithm to handle the large- scale colorful traveling salesman problem. Expert Systems with Applications, v. 67, p. 148–162.
Perez, J. e Consoli, S. (2015), On the minimum labelling spanning bi-connected subgraph problem. Annals ofMIC 2015: The XI Metaheuristics International Conference, arXiv preprint arXiv:1505.01742
Zhang, P. Efficient algorithms for the label cut problems. Theory and Applications of Models ofComputation, p. 259–270. Springer, 2014.
