Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 27 de julio de 2024
  

Un nuevo resultado sobre la complejidad del problema del p-centro.

Título inglés A new result on the complexity of the p-center problem.
Título español Un nuevo resultado sobre la complejidad del problema del p-centro.
Autor/es Moreno Pérez, José Andrés
Organización Dep. Estad. Inv. Oper. Fac. Mat. Univ. La Laguna, La Laguna (Tenerife), España
Revista 0213-8204
Publicación 1990, 5 (1): 61-71, 14 Ref.
Tipo de documento articulo
Idioma Español
Resumen español Sea G un grafo no dirigido con n vértices y m aristas. Un p-Centro de G es un conjunto de p puntos en el que se minimiza la distancia al vértice más lejano. Esta distancia mínima es el p-Radio de G. Un Centro Local es un punto c a la misma distancia (llamada rango del centro local) de un conjunto no vacío de vértices que no son todos accesibles a través de un mismo vértice adyacente a c. Todo p-radio es el rango de algún centro local, por tanto, para resolver el problema del p-centro basta encontrar el menor rango r tal que existe un conjunto de p puntos que cubren a todos los vértices dentro de una distancia r. Este valor r es el p-radio y el correspondiente conjunto es un p-centro. Para encontrar estos conjuntos basta considerar los r-Extremos, puntos a distancia r de algún vértice. En este trabajo se utilizan los r-extremos para construir un sencillo algoritmo de complejidad O(mP·nP+1·log n) que es comparado experimentalmente con el procedimiento de relajación de Handler (1979).
Clasificación UNESCO 120403
Palabras clave español Teoría de grafos ; Grafos
Código Z-Math Zbl 0692.90042
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es