Brunel University Research Archive (BURA) >
University >
Publications >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/506

Title: Mejora de la exploración y la explotación de las heurísticas constructivas para el MLSTP
Authors: Consoli, S
Moreno-Pérez, J A
Mladenović, N
Darby-Dowman, K
Keywords: Árbol Generador
Minimum Labelling Spanning Tree Problem
Heurística constructiva
Análisis estadístico no paramétrico
Publication Date: 2007
Publisher: Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados
Abstract: En este trabajo se proponen dos mejoras para aumentar la explotación y la exploración del clásico algoritmo constructivo MVCA para el problema del árbol generador etiquetado mínimo (Minimum Labelling Spanning Tree Problem; MLSTP). Se describe la aplicación de contrastes de hipótesis no paramétricos para contrastar tales mejoras. En el MLSTP se parte de un grafo conexo con aristas de distinto tipo y se trata de encontrar el árbol generador con las aristas más parecidas posible. Cada tipo de arista viene identificado por un color o etiqueta y el árbol generador óptimo es aquel que usa el menor número de colores. Los tiempos y soluciones obtenidas son comparables a los mejores resultados aparecidos en la literatura para el MLSTP.
URI: http://bura.brunel.ac.uk/handle/2438/506
Appears in Collections:Mathematical Science
Publications
Dept of Mathematics Research Papers

Files in This Item:

File Description SizeFormat
MAEB07MLSTP.pdf625.1 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.