Hardprob/Minimum Bounded Diameter Augmentation — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, положительное целое <m>D<\vert V\vert</m>. * Найти дополняющий набор…») |
(нет различий)
|
Версия 23:15, 7 апреля 2023
- Граф , положительное целое .
- Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
- Минимизировать размер дополняющего множества .
Задача в лаб22 (рид-онли просмотр)