Un algoritmo exacto para el problema del árbol generador mínimo con una restricción de tipo mochila

Abstract

El problema del arbol generador mnimo en un grafo no dirigido con un unico peso asociado a cada una de sus aristas es bien conocido por su utilidad practica, y actualmente se encuentra bien resuelto. Este problema puede extenderse de forma natural sin mas que considerar un vector de pesos u objetivos asociado a cada una de sus aristas, dando lugar a un modelo mucho mas rico pero tremendamente mas difcil de tratar. En este trabajo consideramos un grafo no dirigido con un vector bidimensional de pesos asociado a sus aristas, sobre el que se estudia la obtencion de un arbol generador que minimice uno de los pesos, sujeto a una restriccion de tipo mochila sobre el otro. Para resolver este problema se propone un algoritmo basado en una enumeracion de arboles ordenados respecto a cierta combinacion ponderada de los pesos dados, elegida con el n de acelerar el acercamiento a la solucion optima y, al mismo tiempo, reducir el numero de arboles generados.