# P-Center

Перейти к:навигация, поиск

$\,p$-Center$\,p$-центр.

A $\,p$-center of $\,G = (V,E)$ is a set $C \subseteq V$ that realizes the $\,p$-radius of $\,G$.

The $\,p$-center problem is one of the main problems in facility location theory. For general graphs, the problem of finding $\,p$-centers is $\,NP$-hard. Polynomial algorithms for the $\,p$-center problem are known only for trees and almost-trees. The best known algorithms have time complexity ${\mathcal O}(|V|)$ for unweighted trees and ${\mathcal O}(|V|\cdot \log^{2}|V|)$ for weighted trees.

## Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.