Estructuras jerárquicas de mínima extensión restringida por grados en grafos
Autores: Molnar, Miklos
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Estructuras jerárquicas de mínima extensión restringida por grados en grafos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
árbol de expansión mínima
Grafos
Restricciones de grado
Problema NP-duro
árboles de expansión
Algoritmo heurístico
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
El problema del árbol de expansión mínimo en grafos bajo restricciones de grado de tipo presupuesto (DCMST) es un problema NP-duro bien conocido. Los árboles de expansión no siempre existen y el óptimo no puede aproximarse dentro de un factor constante. Recientemente, se han propuesto soluciones para resolver problemas de expansión con restricciones de grado en el caso de capacidades momentáneas limitadas de los nodos. Para un nodo dado, la restricción representa un grado limitado del nodo para cada visita. Encontrar la solución con el costo mínimo es NP-duro y los algoritmos relacionados no son triviales. Este documento se centra en este nuevo problema de expansión con límites de grado tipo capacidad heterogéneos. La solución de costo mínimo corresponde a una estructura relacionada con el grafo, es decir, una jerarquía. Estudiamos las condiciones de su existencia y proponemos su cálculo exacto, un algoritmo heurístico y su aproximación.
Descripción
El problema del árbol de expansión mínimo en grafos bajo restricciones de grado de tipo presupuesto (DCMST) es un problema NP-duro bien conocido. Los árboles de expansión no siempre existen y el óptimo no puede aproximarse dentro de un factor constante. Recientemente, se han propuesto soluciones para resolver problemas de expansión con restricciones de grado en el caso de capacidades momentáneas limitadas de los nodos. Para un nodo dado, la restricción representa un grado limitado del nodo para cada visita. Encontrar la solución con el costo mínimo es NP-duro y los algoritmos relacionados no son triviales. Este documento se centra en este nuevo problema de expansión con límites de grado tipo capacidad heterogéneos. La solución de costo mínimo corresponde a una estructura relacionada con el grafo, es decir, una jerarquía. Estudiamos las condiciones de su existencia y proponemos su cálculo exacto, un algoritmo heurístico y su aproximación.