Resumen

Esta investigación abordó el problema cuadrático de árbol de recubrimiento mínimo (quadratic minimum spanning tree problem, QMSTP), conocido como NP-hard. Dado un grafo completo, el QMSTP consiste en determinar un árbol de recubrimiento mínimo que considera los costos de interacción entre pares de aristas a ser modeladas. Se trazó un procedimiento de relajación de Lagrange y se desarrolló un algoritmo de búsqueda local eficiente con tabu thresholding. Los experimentos computacionales se reportaron sobre instancias de pruebas generadas de modo aleatorio.

• Materias:Administración Administración de empresas Arquitectura de computadores Investigación operacional
• Subjects:Management Business enterprises Computer architecture Operations research
• Palabras claves:Ciencias de la administración, Teoría de grafos, Modelos de redes, Problema del árbol de recubrimiento mínimo, Problema cuadrático del árbol de recubrimiento mínimo, NP-hard, Relajación de lagrange, búsqueda local, Experimentos computacionales
• Keywords:Administration sciences, Graph theory, Network models, Minimum coating tree problem, Minimum coating tree quadratic Problem, NP-hard, Lagrange relaxation, Local search, Computational experiments