Resumen

Los problemas de localización existen en el mundo real y tratan principalmente de encontrar ubicaciones óptimas para instalaciones en una red, como servidores de red, hospitales y centros comerciales. El problema de localización inversa también se plantea a menudo en la práctica y se ha investigado intensamente en la literatura. Como problema típico de localización inversa, en este trabajo se analiza el problema inverso de la mediana 1 en redes de árboles con longitudes de arista reales variables, que consiste en modificar las longitudes de arista con un coste total mínimo de forma que un vértice dado se convierta en una mediana 1 de la red de árboles con respecto a las nuevas longitudes de arista. En primer lugar, se demuestra que este problema puede resolverse en tiempo lineal con longitudes de arista variables no negativas. Para el caso en que se permiten longitudes de arista negativas, se demuestra la dureza NP bajo distancia Hamming, y se presentan algoritmos de tiempo fuertemente polinómico bajo normas l1 y l∞, respectivamente.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:problema típico de localización inversa, longitudes de arista variables no negativas, longitudes de arista variables reales, problema de localización inversa, coste total mínimo, longitudes de arista negativas, nuevas longitudes de arista, algoritmos de tiempo polinómico, distancia hamming, problemas de localización
• Keywords:typical inverse location problem, variable nonnegative edge lengths, variable real edge lengths, inverse location problem, minimum total cost, negative edge lengths, new edge lengths, polynomial time algorithms, hamming distance, location problems