http://pco.iis.nsk.su/grapp/index.php?title=P-Center&feed=atom&action=history
P-Center - История изменений
2024-03-28T17:22:19Z
История изменений этой страницы в вики
MediaWiki 1.39.3
http://pco.iis.nsk.su/grapp/index.php?title=P-Center&diff=10319&oldid=prev
KEV в 05:14, 1 ноября 2012
2012-11-01T05:14:51Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ru">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 12:14, 1 ноября 2012</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''<math>p</math>-Center''' -<del style="font-weight: bold; text-decoration: none;">-- </del><math>p</math>-центр. </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''<math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-Center''' <ins style="font-weight: bold; text-decoration: none;">— [[p</ins>-<ins style="font-weight: bold; text-decoration: none;">Центр|</ins><math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-центр<ins style="font-weight: bold; text-decoration: none;">]]</ins>. </div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>A '''<math>p</math>-center''' of <math>G = (V,E)</math> is a set <math>C \subseteq V</math> that</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>A '''<math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-center''' of <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G = (V,E)</math> is a set <math>C \subseteq V</math> that</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>realizes the ''<math>p</math>-radius'' of <math>G</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>realizes the ''<ins style="font-weight: bold; text-decoration: none;">[[p-Radius|</ins><math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-radius<ins style="font-weight: bold; text-decoration: none;">]]</ins>'' of <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>G</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The <math>p</math>-center problem is one of the main problems in facility location</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-center problem is one of the main problems in facility location</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>theory. For general graphs, the problem of finding <math>p</math>-centers is</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>theory. For <ins style="font-weight: bold; text-decoration: none;">[[general graph|</ins>general graphs<ins style="font-weight: bold; text-decoration: none;">]]</ins>, the problem of finding <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-centers is</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">''</del>NP<del style="font-weight: bold; text-decoration: none;">''</del>hard. Polynomial algorithms for the <math>p</math>-center problem are known</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><math>\,</ins>NP<ins style="font-weight: bold; text-decoration: none;"></math>-</ins>hard. Polynomial algorithms for the <math><ins style="font-weight: bold; text-decoration: none;">\,</ins>p</math>-center problem are known</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>only for trees and almost-trees. The best known algorithms have time</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>only for <ins style="font-weight: bold; text-decoration: none;">[[tree|</ins>trees<ins style="font-weight: bold; text-decoration: none;">]] </ins>and <ins style="font-weight: bold; text-decoration: none;">[[almost-tree|</ins>almost-trees<ins style="font-weight: bold; text-decoration: none;">]]</ins>. The best known algorithms have time</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>complexity <math>{\mathcal O}(|V|)</math> for unweighted trees and <math>{\mathcal O}(|V|\cdot</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>complexity <math>{\mathcal O}(|V|)</math> for unweighted trees and <math>{\mathcal O}(|V|\cdot</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>\log^{2}|V|)</math> for weighted trees.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>\log^{2}|V|)</math> for <ins style="font-weight: bold; text-decoration: none;">[[weighted graph|</ins>weighted trees<ins style="font-weight: bold; text-decoration: none;">]].</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Литература==</ins></div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009</ins>.</div></td></tr>
</table>
KEV
http://pco.iis.nsk.su/grapp/index.php?title=P-Center&diff=6453&oldid=prev
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…»
2011-02-24T08:53:40Z
<p>Новая страница: «'''<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…»</p>
<p><b>Новая страница</b></p><div>'''<math>p</math>-Center''' --- <math>p</math>-центр. <br />
<br />
A '''<math>p</math>-center''' of <math>G = (V,E)</math> is a set <math>C \subseteq V</math> that<br />
realizes the ''<math>p</math>-radius'' of <math>G</math>.<br />
<br />
The <math>p</math>-center problem is one of the main problems in facility location<br />
theory. For general graphs, the problem of finding <math>p</math>-centers is<br />
''NP''hard. Polynomial algorithms for the <math>p</math>-center problem are known<br />
only for trees and almost-trees. The best known algorithms have time<br />
complexity <math>{\mathcal O}(|V|)</math> for unweighted trees and <math>{\mathcal O}(|V|\cdot<br />
\log^{2}|V|)</math> for weighted trees.</div>
Glk