4624
правки
P-Center: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''<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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>p</math>-Center''' - | '''<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 | ||
<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. | |||