Hardprob/Maximum Integral K-Multicommodity Flow On Trees

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

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

---

Код в «maximum-integral-k-multicommodity-flow-on-trees.ipynb» на гитлаб или живьем в лабе

---

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

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

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

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