Resumen

En un problema de mejora de la ruta más corta bajo distancia Hamming unitaria (denotado por SPIUH), se proporciona un grafo ponderado por aristas con un conjunto de pares fuente-terminal; necesitamos modificar las longitudes de las aristas con un costo mínimo bajo distancia Hamming unitaria de manera que las distancias modificadas de las rutas más cortas estén acotadas por valores dados. El problema SPIUH en una red arbórea se formula como un modelo de programación entera 0-1. Se han diseñado algunos algoritmos de tiempo polinomial fuertes para los problemas en algunas redes arbóreas especiales. En primer lugar, se proponen dos algoritmos voraces para problemas en redes en cadena y redes de estrella-árbol especiales, respectivamente. En segundo lugar, se presenta un algoritmo de tiempo polinomial fuerte para el problema con una única fuente y rutas restringidas. Finalmente, se proporciona un algoritmo heurístico y sus experimentos computacionales para el problema SPIUH en grafos generales.

• Materias:Modelado matemático Modelo de red neuronal Tasa de convergencia Aritmética Ondículas libres
• Subjects:Mathematical modeling Neural network model Convergence rate Arithmetic Free wavelets
• Palabras claves:Grafo ponderado por aristas; Caminos más cortos; Distancia de Hamming unitaria; Problema SPIUH; Red arborescente; Modelo de programación entera
• Keywords:Edge weighted graph; Shortest paths; Unit Hamming distance; SPIUH problem; Arborescent network; Integer programming model