Hardprob/Maximum Integral K-Multicommodity Flow On Trees

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

• Дерево T=(V,E), пропускная способность на ребрах c: E → N, k пар вершин .
• Найти поток , для каждой пары , такой что , где , если e лежит на (единственном, тут дерево) пути из s_i в t_i, и 0 в противном случае.
• Максимизировать сумму потоков

---

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

---

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

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

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

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