A new result on the complexity of the p-center problem.

@article{MorenoPérez1990,
abstract = {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).},
author = {Moreno Pérez, José Andrés},
journal = {Trabajos de Investigación Operativa},
keywords = {Teoría de grafos; Grafos; facility location; undirected graph; p-center; p-radius; local center},
language = {spa},
number = {1},
pages = {61-71},
title = {Un nuevo resultado sobre la complejidad del problema del p-centro.},
url = {http://eudml.org/doc/40611},
volume = {5},
year = {1990},
}

TY - JOUR
AU - Moreno Pérez, José Andrés
TI - Un nuevo resultado sobre la complejidad del problema del p-centro.
JO - Trabajos de Investigación Operativa
PY - 1990
VL - 5
IS - 1
SP - 61
EP - 71
AB - 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).
LA - spa
KW - Teoría de grafos; Grafos; facility location; undirected graph; p-center; p-radius; local center
UR - http://eudml.org/doc/40611
ER -