Просмотр исходного текста страницы Hardprob/Minimum Independent Dominating Set

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
Граф  <m>G=\left(V,E\right)</m>.

Найти независимый доминирующий набор вершин <em>G</em>, т.е. подмножество
<m>V' \subseteq V</m>, такое, что для всех <m>u\in V-V'</m> есть 
* <m>v\in V'</m>
* ребро <m>(u,v) \in E</m>, 
* и при этом нет двух вершин в <em>V'</em> соединенных ребром из <em>E</em>.

Минимизировать мощность доминирующего набора вершин, <m>\vert V'\vert</m>.

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
----
<small>

{{ViggoCode|node14}}
{{GDCode|GT2}}
<!-- * [    Задача в википедии] -->
</small>
<!-- end -->

[[Категория:ClassicHardProblems]]