Problema de Steiner con Restricción de Grado en Grafos con Restricciones de Capacidad
Autores: Molnar, Miklos
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Problema de Steiner con Restricción de Grado en Grafos con Restricciones de Capacidad
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
El problema de Steiner
Grafo
Restricciones de grado
árbol de expansión
Jerarquías
NP-duro
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
El problema de Steiner restringido por grados en grafos es bien conocido en la literatura. En un grafo no dirigido, se asocian límites de grado enteros positivos con los nodos y costos positivos con las aristas. El objetivo es encontrar el árbol de costo mínimo que abarca un conjunto dado de nodos respetando los límites de grado. Como se sabe, no siempre es posible encontrar un árbol que cumpla con las restricciones. El problema difiere cuando los nodos pueden participar múltiples veces en la cobertura y las restricciones representan un grado limitado (una capacidad) para cada ocurrencia de los nodos. El óptimo corresponde a una estructura relacionada con el grafo, es decir, a una jerarquía. Encontrar la solución a este problema particular de Steiner es NP-duro. Investigamos las condiciones de su existencia y su cálculo exacto. La ganancia de las jerarquías se demuestra resolviendo ILPs para calcular jerarquías y árboles. Las ventajas de las jerarquías abarcadoras son concluyentes: (1) las jerarquías abarcadoras se pueden encontrar en algunos casos donde los árboles abarcadores que cumplen con las restricciones de grado no existen; (2) el costo de la jerarquía puede ser menor incluso si el árbol de Steiner que satisface las restricciones existe.
Descripción
El problema de Steiner restringido por grados en grafos es bien conocido en la literatura. En un grafo no dirigido, se asocian límites de grado enteros positivos con los nodos y costos positivos con las aristas. El objetivo es encontrar el árbol de costo mínimo que abarca un conjunto dado de nodos respetando los límites de grado. Como se sabe, no siempre es posible encontrar un árbol que cumpla con las restricciones. El problema difiere cuando los nodos pueden participar múltiples veces en la cobertura y las restricciones representan un grado limitado (una capacidad) para cada ocurrencia de los nodos. El óptimo corresponde a una estructura relacionada con el grafo, es decir, a una jerarquía. Encontrar la solución a este problema particular de Steiner es NP-duro. Investigamos las condiciones de su existencia y su cálculo exacto. La ganancia de las jerarquías se demuestra resolviendo ILPs para calcular jerarquías y árboles. Las ventajas de las jerarquías abarcadoras son concluyentes: (1) las jerarquías abarcadoras se pueden encontrar en algunos casos donde los árboles abarcadores que cumplen con las restricciones de grado no existen; (2) el costo de la jerarquía puede ser menor incluso si el árbol de Steiner que satisface las restricciones existe.