Hardprob/Minimum Tree Width

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

• Граф G=(V,E).
• Декомпозиция на деревья, т.е. пара , где — некое дерево, и коллекция подмножеств вершин V, такая, что
  • для любого существует
  • для любого множество образует связное поддерево T.
• Минимизировать ширину дерева в декомпозиции на деревья, т.е. .

---

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

---

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

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

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

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