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. | |||
Текущая версия от 12:14, 1 ноября 2012
[math]\displaystyle{ \,p }[/math]-Center — [math]\displaystyle{ \,p }[/math]-центр.
A [math]\displaystyle{ \,p }[/math]-center of [math]\displaystyle{ \,G = (V,E) }[/math] is a set [math]\displaystyle{ C \subseteq V }[/math] that realizes the [math]\displaystyle{ \,p }[/math]-radius of [math]\displaystyle{ \,G }[/math].
The [math]\displaystyle{ \,p }[/math]-center problem is one of the main problems in facility location theory. For general graphs, the problem of finding [math]\displaystyle{ \,p }[/math]-centers is [math]\displaystyle{ \,NP }[/math]-hard. Polynomial algorithms for the [math]\displaystyle{ \,p }[/math]-center problem are known only for trees and almost-trees. The best known algorithms have time complexity [math]\displaystyle{ {\mathcal O}(|V|) }[/math] for unweighted trees and [math]\displaystyle{ {\mathcal O}(|V|\cdot \log^{2}|V|) }[/math] for weighted trees.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.