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>&#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-Center&#039;&#039;&#039; -<del style="font-weight: bold; text-decoration: none;">-- </del>&lt;math&gt;p&lt;/math&gt;-центр.  </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>&#039;&#039;&#039;&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-Center&#039;&#039;&#039; <ins style="font-weight: bold; text-decoration: none;">— [[p</ins>-<ins style="font-weight: bold; text-decoration: none;">Центр|</ins>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-центр<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 &#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-center&#039;&#039;&#039; of &lt;math&gt;G = (V,E)&lt;/math&gt; is a set &lt;math&gt;C \subseteq V&lt;/math&gt; 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 &#039;&#039;&#039;&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-center&#039;&#039;&#039; of &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G = (V,E)&lt;/math&gt; is a set &lt;math&gt;C \subseteq V&lt;/math&gt; 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 &#039;&#039;&lt;math&gt;p&lt;/math&gt;-radius&#039;&#039; of &lt;math&gt;G&lt;/math&gt;.</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 &#039;&#039;<ins style="font-weight: bold; text-decoration: none;">[[p-Radius|</ins>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-radius<ins style="font-weight: bold; text-decoration: none;">]]</ins>&#039;&#039; of &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>G&lt;/math&gt;.</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 &lt;math&gt;p&lt;/math&gt;-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 &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-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 &lt;math&gt;p&lt;/math&gt;-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 &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-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;">&#039;&#039;</del>NP<del style="font-weight: bold; text-decoration: none;">&#039;&#039;</del>hard. Polynomial algorithms for the &lt;math&gt;p&lt;/math&gt;-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;">&lt;math&gt;\,</ins>NP<ins style="font-weight: bold; text-decoration: none;">&lt;/math&gt;-</ins>hard. Polynomial algorithms for the &lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\,</ins>p&lt;/math&gt;-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 &lt;math&gt;{\mathcal O}(|V|)&lt;/math&gt; for unweighted trees and &lt;math&gt;{\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 &lt;math&gt;{\mathcal O}(|V|)&lt;/math&gt; for unweighted trees and &lt;math&gt;{\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|)&lt;/math&gt; 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|)&lt;/math&gt; 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>Новая страница: «&#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-Center&#039;&#039;&#039; --- &lt;math&gt;p&lt;/math&gt;-центр. A &#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-center&#039;&#039;&#039; of &lt;math&gt;G = (V,E)&lt;/math&gt; is a set &lt;math&gt;C \subseteq V&lt;/math&gt; that realize…»</p> <p><b>Новая страница</b></p><div>&#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-Center&#039;&#039;&#039; --- &lt;math&gt;p&lt;/math&gt;-центр. <br /> <br /> A &#039;&#039;&#039;&lt;math&gt;p&lt;/math&gt;-center&#039;&#039;&#039; of &lt;math&gt;G = (V,E)&lt;/math&gt; is a set &lt;math&gt;C \subseteq V&lt;/math&gt; that<br /> realizes the &#039;&#039;&lt;math&gt;p&lt;/math&gt;-radius&#039;&#039; of &lt;math&gt;G&lt;/math&gt;.<br /> <br /> The &lt;math&gt;p&lt;/math&gt;-center problem is one of the main problems in facility location<br /> theory. For general graphs, the problem of finding &lt;math&gt;p&lt;/math&gt;-centers is<br /> &#039;&#039;NP&#039;&#039;hard. Polynomial algorithms for the &lt;math&gt;p&lt;/math&gt;-center problem are known<br /> only for trees and almost-trees. The best known algorithms have time<br /> complexity &lt;math&gt;{\mathcal O}(|V|)&lt;/math&gt; for unweighted trees and &lt;math&gt;{\mathcal O}(|V|\cdot<br /> \log^{2}|V|)&lt;/math&gt; for weighted trees.</div> Glk