M. Landete Ruiz, A. Marín Pérez, J. L. Sainz-Pardo Auñón
Los conmutadores son nodos con grado mayor que dos. En esta exposición se analiza el problema de localización de conmutadores sobre el árbol generador de un grafo. Localizar un conmutador implica dos tipos de costes, los costes de conexión usuario-conmutador y el coste de instalación, siendo la finalidad el minimizar la suma de ambos.
Este problema de localización es una generalización de los problemas: 'árbol de expansión con menor número de vértices de ramificación' y 'árbol de expansión con menor suma de grados'. Se propone un método exacto empleando un algoritmo de descomposición en bloques de forma que, para cada bloque, se resuelve un modelo de programación entera. En aquellos grafos donde no es posible la descomposición en bloques, se propone un método matemático-heurístico basado en la resolución exacta de un grafo reducido obtenido al suprimir algunas aristas del grafo original y que por tanto se beneficia del estudio hecho en el caso de la descomposición en bloques.
Palabras clave / Keywords: árboles, vértices de corte, bloques, conmutador
Programado
Sesión M07 Grafos, Distribuciones, rutas y transporte
30 de mayo de 2018 17:10
Sala 1
