A polyhedral approach to the generalized minimum labeling spanning tree problem

Thiago Gouveia da Silva1,2,3, Serigne Gueye1, Philippe Michelon1, Luiz Satoru Ochi3, Lucídio dos Anjos Formiga Cabral4
1LIA-UAPV, Université d’Avignon, 339 Chemin des Meinajaries, 84140, Avignon, France.
2IFPB, Instituto Federal de Educação, Ciência e Tecnologia da Paraíba, 256 Av. João da Mata, CEP: 58.015-020, João Pessoa, PB, Brazil.
3UFF, Universidade Federal Fluminense, 156 R. Passo da Pátria, CEP: 24210-240, Niterói, RJ, Brazil.
4UFPB, Universidade Federal da Paraíba, R. dos Escoteiros, CEP: 58055-000, João Pessoa, PB, Brazil.

Tóm tắt

Từ khóa


Tài liệu tham khảo

Brüggemann, 2003, Local search for the minimum label spanning tree problem with bounded color classes, Oper Res Lett, 31, 195, 10.1016/S0167-6377(02)00241-9

Captivo, 2009, A mixed integer linear formulation for the minimum label spanning tree problem, Comput Oper Res, 36, 3082, 10.1016/j.cor.2009.02.003

Cerulli, 2005, Metaheuristics comparison for the minimum labelling spanning tree problem, 93, 10.1007/0-387-23529-9_7

Chang, 1997, The minimum labeling spanning trees, Inf Process Lett, 63, 277, 10.1016/S0020-0190(97)00127-0

Chen, 2008, Comparison of heuristics for solving the gmlst problem, 191

Chwatal AM, Raidl GR (2010) Solving the minimum label spanning tree problem by ant colony optimization. In: Arabnia HR, Hashemi RR, Solo AMG (eds) GEM. CSREA Press, Las Vegas, pp 91–97. ISBN: 1-60132-145-7

Chwatal, 2011, Solving the minimum label spanning tree problem by mathematical programming techniques, Adv Oper Res, 10.1155/2011/143732

Chwatal AM, Raidl GR, Oberlechner K (2009) Solving an extended minimum label spanning tree problem to compress fingerprint templates. J Math Model Algorithms 8(3):293–334. previous technical report version at https://www.ac.tuwien.ac.at/files/pub/chwatal-08a.pdf

Consoli, 2009, Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem, Eur J Oper Res, 196, 440, 10.1016/j.ejor.2008.03.014

Consoli, 2015, Solving the minimum labelling spanning tree problem by intelligent optimization, Appl Soft Comput, 28, 440, 10.1016/j.asoc.2014.12.020

Granata, 2013, Maximum flow problems and an np-complete variant on edge-labeled graphs, 1913

Krumke, 1998, On the minimum label spanning tree problem, Inf Process Lett, 66, 81, 10.1016/S0020-0190(98)00034-9

Van-Nes R (2002) Design of multimodal transport networks: a hierachical approach. PhD thesis. Delft University

Wan, 2002, A note on the minimum label spanning tree, Inf Process Lett, 84, 99, 10.1016/S0020-0190(02)00230-2

Wolsey, 2014

Xiong, 2005, A one-parameter genetic algorithm for the minimum labeling spanning tree problem, IEEE Trans Evolut Comput, 9, 55, 10.1109/TEVC.2004.840145

Xiong, 2005, Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem, Oper Res Lett, 33, 77, 10.1016/j.orl.2004.03.004

Xiong, 2006, Improved heuristics for the minimum label spanning tree problem, IEEE Trans Evol Comput, 10, 700, 10.1109/TEVC.2006.877147