Resumen

Este documento considera el problema general de expansión de capacidad de ruta (GCEP) para los operadores de telecomunicaciones. Investigamos la equivalencia polinómica entre el problema GCEP y el problema de ruta más corta restringida (CSP) y presentamos un algoritmo pseudopolinómico para el problema GCEP, sin importar si el grafo es acíclico o no. Además, investigamos dos versiones especiales del problema GCEP. Para el problema de la ruta de expansión de capacidad con el número mínimo de arcos (MN-CEP), damos un algoritmo fuertemente polinómico basado en la programación dinámica. Para el problema de la ruta más corta de expansión de capacidad de costo mínimo (MCESP), damos un algoritmo fuertemente polinómico mediante la construcción de una red de rutas más cortas.

• 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:Problema de expansión de capacidad general; Operadores de telecomunicaciones; Equivalencia polinómica; Problema de camino más corto restringido; Algoritmo pseudopolinómico; Acíclico; Problema de expansión de capacidad de número mínimo de arcos; Programación dinámica; Problema de camino más corto de expansión de capacidad de costo mínimo; Red de caminos más cortos
• Keywords:General capacity expansion path problem; Telecommunication operators; Polynomial equivalence; Constrained shortest path problem; Pseudopolynomial algorithm; Acyclic; Minimum number arc capacity expansion path problem; Dynamic programming; Minimum-cost capacity expansion shortest path problem; Shortest paths network