Hardprob/Maximum Disjoint Connecting Paths
Материал из DISCOPAL
Версия от 22:58, 17 апреля 2023; StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w),\s*(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, \3<sub>\4</sub>, …, \5<sub>\6</sub></em>)
- Мультиграф G=(V,E), коллекция пар вершин .
- Найти коллекцию непересекающихся по ребрам путей в G соединающих некоторые из пар , т.е. путь это последовательность вершин u1, u2, …, um, такая что для некоторого i, , и для всех j, .
- Максимизация числа пар вершин , которые будут соединены этими путями.
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND40»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.