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


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.