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

  1. Marianela Carrillo Fernández
  2. Jesús Manuel Jorge Santiso
Book:
XXXI Congreso Nacional de Estadística e Investigación Operativa ; V Jornadas de Estadística Pública: Murcia, 10-13 de febrero de 2009 : Libro de Actas

Publisher: Universidad de Murcia. Departamento de Estadística e Investigación Operativa

ISBN: 978-84-691-8159-1

Year of publication: 2009

Pages: 316

Congress: Congreso Nacional de Estadística e Investigación Operativa (31. 2009. Murcia)

Type: Conference paper

Export: RIS

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.