Hardprob/Minimum Bounded Diameter Augmentation

Ссылки сюда (2) →

• Граф G=(V,E), положительное целое .
• Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
• Минимизировать размер дополняющего множества |E'|.

---

Задача в лаб22 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.