logo móvil
Contáctanos

Estructuras jerárquicas de mínima extensión restringida por grados en grafos

Autores: Molnar, Miklos

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro