Hardprob/Minimum Unsplittable Flow

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

• Граф G=(V,E), емкости на ребрах , вершина-источник s, коллекция вершин-стоков t₁, …, t_k, с привязанными неотрицательными целочисленными запросами , такое, что .
• Найти для каждого типа i единый путь , такой что все запросы удовлетворены, и полный поток проходящий через любое ребро e ограничено c(e).
• Минимизировать , где f(e) это полный поток проходящий через e.

---

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

---

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

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

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

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