Resumen

Sea un grafo simple no dirigido completo con conjuntos de vértices y aristas , respectivamente. En este artículo, consideramos el problema del árbol de expansión mínimo con restricciones de grado (DCMST), que consiste en encontrar un subárbol de de costo mínimo formado con al menos vértices de donde el grado de cada vértice es menor o igual a un valor entero . En particular, en este artículo, consideramos valores de grado de . Nótese que DCMST generaliza simultáneamente tanto el problema clásico de árbol de expansión mínimo con restricciones de grado como el de grado . En particular, cuando , se reduce a un problema de camino hamiltoniano. Los dominios de aplicación donde DCMST puede adaptarse o utilizarse directamente incluyen estructuras de red de troncal en telecomunicaciones, ubicación de instalaciones y redes de transporte, por nombrar algunos. Es fácil ver en la literatura que hasta ahora el problema DCMST no ha sido estudiado en profundidad. Por lo tanto, nuestras principales contribuciones en este artículo pueden ser resaltadas de la siguiente

• Materias:Big Data Gestión de riesgos Administración de información Red neuronal Teoría de redes
• Subjects:Big Data Risk management Information management Neural network Network Theory
• Palabras claves:Grafo completo; Problema DCMST; Con restricción de grado; árbol de expansión mínimo; Optimización de colonias de hormigas; Q-learning
• Keywords:Complete graph; DCMST problem; Degree-constrained; Minimum spanning tree; Ant colony optimization; Q-learning