P-Center: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''<math>p</math>-Center''' --- <math>p</math>-центр. A '''<math>p</math>-center''' of <math>G = (V,E)</math> is a set <math>C \subseteq V</math> that realize…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''<math>p</math>-Center''' --- <math>p</math>-центр.  
'''<math>\,p</math>-Center''' — [[p-Центр|<math>\,p</math>-центр]].  


A '''<math>p</math>-center''' of <math>G = (V,E)</math> is a set <math>C \subseteq V</math> that
A '''<math>\,p</math>-center''' of <math>\,G = (V,E)</math> is a set <math>C \subseteq V</math> that
realizes the ''<math>p</math>-radius'' of <math>G</math>.
realizes the ''[[p-Radius|<math>\,p</math>-radius]]'' of <math>\,G</math>.


The <math>p</math>-center problem is one of the main problems in facility location
The <math>\,p</math>-center problem is one of the main problems in facility location
theory. For general graphs, the problem of finding <math>p</math>-centers is
theory. For [[general graph|general graphs]], the problem of finding <math>\,p</math>-centers is
''NP''hard. Polynomial algorithms for the <math>p</math>-center problem are known
<math>\,NP</math>-hard. Polynomial algorithms for the <math>\,p</math>-center problem are known
only for trees and almost-trees. The best known algorithms have time
only for [[tree|trees]] and [[almost-tree|almost-trees]]. The best known algorithms have time
complexity <math>{\mathcal O}(|V|)</math> for unweighted trees and <math>{\mathcal O}(|V|\cdot
complexity <math>{\mathcal O}(|V|)</math> for unweighted trees and <math>{\mathcal O}(|V|\cdot
\log^{2}|V|)</math> for weighted trees.
\log^{2}|V|)</math> for [[weighted graph|weighted trees]].
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация