logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro