В теории оптимизации , максимальные задачи потока вовлекают найти посильную поток через сеть потока , который получает максимально возможную скорость потока.
Задачу максимального потока можно рассматривать как частный случай более сложных проблем сетевого потока, таких как проблема циркуляции . Максимальное значение st-потока (т. Е. Потока от источника s к приемнику t) равно минимальной пропускной способности st-отрезка (т. Е. Отрезка s от t) в сети, как указано в max-flow min- теорема сокращения .
История
Задача о максимальном потоке была впервые сформулирована в 1954 г. Т.Е. Харрисом и Ф.С. Россом как упрощенная модель советского железнодорожного движения. [1] [2] [3]
В 1955 году Лестер Р. Форд-младший и Делберт Р. Фулкерсон создали первый известный алгоритм - алгоритм Форда – Фулкерсона . [4] [5] В своей статье 1955 года [4] Форд и Фулкерсон написали, что проблема Харриса и Росса формулируется следующим образом (см. [1] с. 5):
Рассмотрим железнодорожную сеть, соединяющую два города посредством ряда промежуточных городов, где каждому звену сети присвоен номер, обозначающий его пропускную способность. Предполагая установившееся состояние, найдите максимальный поток из одного заданного города в другой.
В их книге потоков в сети , [5] в 1962 году, Ford и Фулкерсон писал:
Она была поставлена авторам весной 1955 года Т. Е. Харрисом, который вместе с генералом Ф. С. Россом (в отставке) сформулировал упрощенную модель движения железнодорожного транспорта и определил эту конкретную проблему как центральную, предложенную в модель [11].
где [11] относится к секретному отчету 1955 года « Основы метода оценки пропускной способности железнодорожной сети » Харриса и Росс [3] (см. [1] стр. 5).
За прошедшие годы были обнаружены различные улучшенные решения проблемы максимального потока, в частности, алгоритм кратчайшего увеличивающегося пути Эдмондса и Карпа и независимо Диница; алгоритм блокировки потока Диница; нажимной алгоритм повторной расстановки меток из Голдберг и Tarjan ; и алгоритм двоичного блокирующего потока Голдберга и Рао. Алгоритмы Шермана [6] и Келнера, Ли, Ореккья и Сидфорда [7] [8] соответственно находят приблизительно оптимальный максимальный поток, но работают только в неориентированных графах.
В 2013 году Джеймс Б. Орлин опубликовал статью, описывающуюалгоритм. [9]
Определение
Сначала введем некоторые обозначения:
- Позволять быть сетью с быть источником и приемником соответственно.
- Если функция на краях тогда его стоимость на обозначается или же
Определение. Емкость ребра максимального количество потоков , которые могут проходить через край. Формально это карта
Определение. Поток представляет собой карту который удовлетворяет следующему:
- Ограничение емкости . Поток ребра не может превышать его пропускную способность, другими словами: для всех
- Сохранение потоков. Сумма потоков, входящих в узел, должна равняться сумме потоков, выходящих из этого узла, за исключением источника и приемника. Или же:
Замечание . Потоки кососимметричны: для всех
Определение. Величина потока является количеством проходящего от источника к раковине потока. Формально для потока это определяется:
Определение. Задача максимального потока состоит в том, чтобы направить как можно больше потока из источника в сток, другими словами, найти поток. с максимальным значением.
Обратите внимание, что может существовать несколько максимальных потоков, и если разрешены произвольные действительные (или даже произвольные рациональные) значения потока (а не только целые числа), существует либо ровно один максимальный поток, либо бесконечно много, поскольку существует бесконечно много линейных комбинаций базовые максимальные потоки. Другими словами, если мы отправим единицы расхода на краю за один максимальный поток, и единиц расхода на в другом максимальном потоке, затем для каждого мы можем отправить единиц на и соответствующим образом направить поток по оставшимся кромкам, чтобы получить еще один максимальный поток. Если значения расхода могут быть любыми действительными или рациональными числами, то таких бесконечно много. значения для каждой пары .
Алгоритмы
В следующей таблице перечислены алгоритмы решения задачи максимального расхода.
Метод | Сложность | Описание |
---|---|---|
Линейное программирование | Ограничения, заданные определением юридического потока . Смотрите линейную программу здесь. | |
Алгоритм Форда – Фулкерсона | Пока существует открытый путь через остаточный граф, отправьте минимум остаточных мощностей на пути. Алгоритм гарантированно завершится, только если все веса рациональны , и в этом случае сумма, добавляемая к потоку на каждом шаге, является, по крайней мере, наибольшим общим делителем весов. В противном случае возможно, что алгоритм не сойдется к максимальному значению. Однако, если алгоритм завершается, гарантируется нахождение максимального значения. | |
Алгоритм Эдмондса – Карпа | Специализация Форда – Фулкерсона, поиск дополнительных путей с помощью поиска в ширину . | |
Алгоритм диника | На каждом этапе алгоритмы строят многоуровневый граф с поиском в ширину на остаточном графе . Максимальный расход на многоуровневом графике можно рассчитать в время, а максимальное количество фаз . В сетях с единичной мощностью алгоритм Динича заканчивается навремя. [ необходима цитата ] | |
Алгоритм MKM (Малхотра, Кумар, Махешвари) [10] | Модификация алгоритма Динича с другим подходом к построению блокирующих потоков. Обратитесь к исходной бумаге . | |
Алгоритм Динича с динамическими деревьями | Структура данных динамических деревьев ускоряет вычисление максимального потока в многоуровневом графе до. | |
Общий алгоритм push – relabel [11] | Алгоритм push relabel поддерживает предварительный поток, то есть функцию потока с возможностью избытка в вершинах. Алгоритм выполняется, пока есть вершина с положительным избытком, т.е. активная вершина в графе. Операция проталкивания увеличивает поток на остаточном ребре, а функция высоты на вершинах управляет тем, через какие остаточные ребра могут протекать потоки. Функция высоты изменяется операцией переназначения. Правильное определение этих операций гарантирует, что результирующая функция потока будет максимальным потоком. | |
Алгоритм push – reabel с правилом выбора вершин FIFO [11] | Вариант алгоритма push-relabel, который всегда выбирает самую последнюю активную вершину и выполняет операции push, пока избыток положительный и есть допустимые остаточные ребра из этой вершины. | |
Алгоритм push – relabel с правилом выбора вершин на максимальном расстоянии [12] | Вариант алгоритма push-relabel, который всегда выбирает самую удаленную вершину из или же (т.е. самая высокая вершина метки), но в остальном действует как алгоритм FIFO. | |
Алгоритм push-relabel с динамическими деревьями [11] | Алгоритм строит деревья ограниченного размера на остаточном графе относительно функции высоты. Эти деревья обеспечивают многоуровневые операции проталкивания, т. Е. Проталкивание по всей траектории насыщения вместо одного края. | |
Алгоритм KRT (King, Rao, Tarjan) [13] | ||
Алгоритм двоичного блокирующего потока [14] | Значение U соответствует максимальной пропускной способности сети. | |
Алгоритм Джеймса Б. Орлина + KRT (Кинг, Рао, Тарджан) [9] | Алгоритм Орлина решает максимальный поток в время в то время как KRT решает это в для . | |
Алгоритм Катурии-Лю-Сидфорда [15] | Методы внутренней точки и усиление кромок с помощью -нормальные потоки. Основан на более раннем алгоритме Мадри, в котором достигнуто время выполнения. [16] | |
Алгоритм BLNPSSSW / BLLSSSW [17] [18] | Методы внутренней точки и динамическое поддержание электрических потоков с детандерными разложениями. | |
Алгоритм Гао-Лю-Пэна [19] | Алгоритм Гао, Лю и Пэна вращается вокруг динамического поддержания дополнительных электрических потоков в основе алгоритма, основанного на методе внутренней точки из [Mądry JACM '16]. Это влечет за собой разработку структур данных, которые в ограниченных настройках возвращают края с большой электрической энергией в график, подвергающийся обновлениям сопротивления. |
Дополнительные алгоритмы см. В Goldberg & Tarjan (1988) .
Теорема об интегральном потоке
Теорема об интегральном потоке утверждает, что
- Если каждое ребро в сети потоков имеет целую пропускную способность, каждый максимальный поток также является целым.
Это немедленно следует из теоремы о максимальном потоке о минимальном разрезе , поскольку, если все ребра имеют целочисленную пропускную способность, каждый минимальный разрез также имеет целую пропускную способность.
Заявление
Проблема максимального расхода с несколькими источниками и несколькими стоками
Учитывая сеть с набором исходников и набор раковин вместо одного источника и одного стока мы должны найти максимальный поток через . Мы можем преобразовать проблему с несколькими источниками и несколькими приемниками в проблему максимального потока, добавив консолидированный источник, подключенный к каждой вершине ви консолидированный сток, соединенный каждой вершиной в(также известный как supersource и supersink ) с бесконечной мощности на каждой кромке (см. 4.1.1.).
Максимальное количество элементов при двудольном сопоставлении
Учитывая двудольный граф , мы должны найти максимальное соответствие мощности в, то есть соответствие, которое содержит максимально возможное количество ребер. Эту задачу можно преобразовать в задачу о максимальном потоке, построив сеть, где
- содержит ребра в направлено из к .
- для каждого а также для каждого .
- для каждого (См. Рис. 4.3.1).
Тогда значение максимального расхода в равен размеру максимального соответствия в .
Минимальное покрытие пути в ориентированном ациклическом графе
Учитывая ориентированный ациклический граф , мы должны найти минимальное количество вершинно-непересекающихся путей, чтобы покрыть каждую вершину в. Мы можем построить двудольный граф из , где
- .
Тогда можно показать, что имеет соответствие размера если и только если имеет вершинно-непересекающееся покрытие пути содержания края и пути, где количество вершин в . Следовательно, проблема может быть решена путем нахождения максимального соответствия мощности в вместо.
Интуитивно, если две вершины совпадают в , то край содержится в . Ясно, что количество ребер в является . Чтобы увидеть это вершинно-не пересекается, рассмотрим следующее:
- Каждая вершина в могут быть либо без подобранных в, в этом случае края не выходят в ; или его можно сопоставить , и в этом случае остается ровно одно ребро в . В любом случае из вершины выходит не более одного ребра. в .
- Аналогично для каждой вершины в - если он совпадает, то есть одно входящее ребро в в ; иначе не имеет входящих ребер в .
Таким образом, ни одна вершина не имеет двух входящих или двух исходящих ребер в , что означает все пути в вершинно-непересекающиеся.
Чтобы показать, что обложка имеет размер , мы начинаем с пустой крышки и постепенно ее наращиваем. Чтобы добавить вершинук обложке, мы можем либо добавить его к существующему пути, либо создать новый путь нулевой длины, начиная с этой вершины. Первый случай применим, когда либо и какой-то путь в обложке начинается в , или же и какой-то путь заканчивается в . Последний случай применим всегда. В первом случае общее количество ребер в крышке увеличивается на 1, а количество путей остается прежним; в последнем случае количество путей увеличивается, а количество ребер остается прежним. Теперь ясно, что после покрытия всех вершин, сумма количества путей и ребер в покрытии равна . Следовательно, если количество ребер в крышке равно, количество путей .
Максимальный поток при вершинных возможностях
Позволять быть сетью. Предположим, что в каждом узле есть пропускная способность в дополнение к пропускной способности ребра, то есть отображение такой, что поток должен удовлетворять не только ограничению пропускной способности и сохранению потоков, но и ограничению пропускной способности вершин
Другими словами, количество потока, проходящего через вершину, не может превышать ее пропускную способность. Чтобы найти максимальный поток через, мы можем преобразовать задачу в задачу о максимальном потоке в исходном смысле, разложив . Во-первых, каждый заменяется на а также , где соединяется ребрами, входящими в а также связан с краями, выходящими из , затем назначьте емкость к краю, соединяющему а также (см. рис. 4.4.1). В этой расширенной сети снято ограничение на пропускную способность вершин, и поэтому проблему можно рассматривать как исходную задачу о максимальном потоке.
Максимальное количество путей от s до t
Учитывая ориентированный граф и две вершины а также , мы должны найти максимальное количество путей из к . У этой проблемы есть несколько вариантов:
1. Пути не должны пересекаться по ребрам. Эту задачу можно преобразовать в задачу о максимальном потоке, построив сеть из , с участием а также быть источником и приемником соответственно, и присвоив каждому ребру пропускную способность . В этой сети максимальный поток составляет если есть рёберно-непересекающиеся пути.
2. Пути должны быть независимыми, т. Е. Вершинно-непересекающимися (кроме а также ). Мы можем построить сеть из с вместимостью вершин, где мощности всех вершин и всех ребер равны . Тогда значение максимального потока равно максимальному количеству независимых путей от к .
3. Помимо того, что пути не пересекаются по ребрам и / или вершинам не пересекаются, они также имеют ограничение длины: мы считаем только пути, длина которых точно равна , или самое большее . Большинство вариантов этой задачи являются NP-полными, за исключением малых значений. [20]
Проблема закрытия
Замыкание ориентированного графа представляет собой набор вершин C , таким образом, что нет края не оставить C . Проблема закрытия - это задача нахождения замыкания с максимальным или минимальным весом в ориентированном графе, взвешенном по вершинам. Ее можно решить за полиномиальное время, используя задачу сведения к максимальному потоку.
Приложения реального мира
Ликвидация бейсбола
В задаче на выбывание по бейсболу в лиге соревнуются n команд. На определенном этапе сезона лиги w i - это количество побед, r i - количество игр, оставшихся до игры для команды i, а r ij - количество игр, оставшихся против команды j . Команда выбывает, если у нее нет шансов закончить сезон на первом месте. Задача задачи выбывания бейсбола состоит в том, чтобы определить, какие команды выбывают в каждой точке в течение сезона. Шварц [21] предложил метод, который сводит эту проблему к максимальному потоку в сети. В этом методе создается сеть, чтобы определить, исключена ли команда k .
Пусть G = ( V , E ) - сеть, где s , t ∈ V - источник и сток соответственно. Один добавляет игровой узел { i , j } с i < j к V и соединяет каждый из них из s ребром с емкостью r ij, которое представляет количество игр между этими двумя командами. Мы также добавляем командный узел для каждой команды и соединяем каждый игровой узел { i , j } с двумя командными узлами i и j, чтобы гарантировать, что один из них выиграет. На этих краях нет необходимости ограничивать величину потока. Наконец, от узла команды i к узлу приемника t делаются ребра, а емкость w k + r k - w i устанавливается так, чтобы не дать команде i выиграть больше, чем w k + r k . Пусть S будет набором всех команд, участвующих в лиге, и пусть. В этом методе утверждается , команда к не устранена , если и только если значение потока размера г ( S - { K }) существует в сети G . В указанной статье доказано, что это значение расхода является максимальным значением расхода от s до t .
Расписание авиакомпаний
В авиационной отрасли серьезной проблемой является планирование работы летных экипажей. Задачу планирования авиалиний можно рассматривать как приложение расширенного максимального сетевого потока. Входными данными этой задачи является набор рейсов F, который содержит информацию о том, где и когда каждый рейс отправляется и прибывает. В одной из версий расписания авиакомпаний цель состоит в том, чтобы составить реальное расписание с максимум k экипажами.
Для решения этой проблемы используется разновидность задачи циркуляции, называемая ограниченной циркуляцией, которая является обобщением задач сетевого потока с добавленным ограничением нижней границы для граничных потоков.
Пусть G = ( V , E ) - сеть с s , t ∈ V в качестве узлов источника и приемника. Для источника и пункта назначения каждого рейса i к V добавляются два узла : узел s i как источник и узел d i как узел назначения рейса i . Также к E добавляются следующие ребра :
- Ребро с пропускной способностью [0, 1] между s и каждым s i .
- Ребро с емкостью [0, 1] между каждыми d i и t .
- Ребро с емкостью [1, 1] между каждой парой s i и d i .
- Граница с пропускной способностью [0, 1] между каждыми d i и s j , если источник s j достижим с разумным количеством времени и затрат из пункта назначения рейса i .
- Ребро с пропускной способностью [0, ∞ ] между s и t .
В упомянутом методе заявлено и доказано, что нахождение значения потока k в G между s и t равносильно нахождению допустимого расписания для полетного набора F с не более чем k экипажами. [22]
Другой вариант расписания авиакомпаний - поиск минимально необходимого экипажа для выполнения всех полетов. Для того , чтобы найти ответ на этот вопрос, двудольный граф G» = ( ∪ B , E ) создаются , где каждый полет имеет копию в множестве A и множество B . Если же плоскость может выполнять полет J после полета я , я ∈ A соединен с J ∈ B . Сопоставление в G ' индуцирует расписание для F, и, очевидно, максимальное двустороннее сопоставление в этом графе дает расписание авиакомпаний с минимальным количеством экипажей. [22] Как упоминается в разделе «Приложение» этой статьи, двустороннее сопоставление с максимальной мощностью является приложением задачи о максимальном потоке.
Проблема обращения – спроса
Есть несколько фабрик, которые производят товары, и несколько деревень, куда товары нужно доставить. Они связаны сетью дорог, каждая из которых имеет пропускную способность c для максимального количества товаров, которые могут проходить по ней. Проблема в том, чтобы определить, есть ли тираж, удовлетворяющий спрос. Эта проблема может быть преобразована в задачу о максимальном расходе.
- Добавьте исходный узел s и добавьте ребра из него в каждый заводской узел f i с мощностью p i, где p i - производительность завода f i .
- Добавьте приемный узел t и добавьте ребра из всех деревень v i в t с пропускной способностью d i, где d i - уровень спроса деревни v i .
Пусть G = ( V , E ) - эта новая сеть. Существует тираж, удовлетворяющий спрос тогда и только тогда, когда:
- Максимальное значение расхода ( G ).
Если существует циркуляция, рассмотрение решения с максимальным потоком даст ответ о том, сколько товаров должно быть отправлено по определенной дороге для удовлетворения потребностей.
Задачу можно расширить, добавив нижнюю границу потока на некоторых ребрах. [23]
Сегментация изображения
В своей книге Клейнберг и Тардос представляют алгоритм сегментации изображения. [25] Они представляют алгоритм для поиска фона и переднего плана в изображении. Точнее, алгоритм принимает растровое изображение в качестве входных данных, моделируемых следующим образом: a i ≥ 0 - вероятность того, что пиксель i принадлежит переднему плану, b i ≥ 0 - вероятность того, что пиксель i принадлежит фону, а p ij - это вероятность того, что пиксель i принадлежит фону. штраф, если два соседних пикселя i и j размещаются один на переднем плане, а другой - на заднем. Цель состоит в том, чтобы найти раздел ( A , B ) набора пикселей, который максимизирует следующее количество
- ,
Действительно, для пикселей в A (рассматривается как на переднем плане), мы получаем в I ; для всех пикселей в B (рассматриваемых как фон) мы получаем b i . На границе между двумя соседними пикселями i и j мы теряем p ij . Это эквивалентно минимизации количества
так как
Теперь мы строим сеть, узлами которой являются пиксель, а также источник и приемник, см. Рисунок справа. Подключаем источник к пикселю i ребром веса a i . Подключаем пиксель i к раковине ребром веса b i . Мы соединяем пиксель i с пикселем j с весом p ij . Теперь осталось вычислить минимальный разрез в этой сети (или, что эквивалентно, максимальный поток). На последнем рисунке показан минимальный срез.
Расширения
1. В задаче потока с минимальными затратами каждое ребро ( u , v) также имеет коэффициент затрат a uv в дополнение к своей пропускной способности. Если поток через край является F уф , то общая стоимость ув е ув . Требуется найти поток заданного размера d с наименьшими затратами. В большинстве вариантов коэффициенты затрат могут быть как положительными, так и отрицательными. Для этой задачи существуют различные полиномиальные алгоритмы.
2. Проблема максимального потока может быть дополнена дизъюнктивными ограничениями : отрицательное дизъюнктивное ограничение говорит, что определенная пара ребер не может одновременно иметь ненулевой поток; а положительное дизъюнктивное ограничение говорит , что в некоторых парах ребер, по меньшей мере , один должна иметь ненулевой поток. При отрицательных ограничениях задача становится NP-трудной даже для простых сетей. При положительных ограничениях проблема является полиномиальной, если разрешены дробные потоки, но может быть сильно NP-трудной, когда потоки должны быть целыми. [26]
Рекомендации
- ^ a b c Schrijver, A. (2002). «Об истории перевозки и проблемах максимального расхода». Математическое программирование . 91 (3): 437–445. CiteSeerX 10.1.1.23.5134 . DOI : 10.1007 / s101070100259 . S2CID 10210675 .
- ^ Гасс, Саул I .; Асад, Арджанг А. (2005). «Математические, алгоритмические и профессиональные разработки исследования операций с 1951 по 1956 год». Аннотированный график исследования операций . Международная серия исследований операций и управления. 75 . С. 79–110. DOI : 10.1007 / 0-387-25837-X_5 . ISBN 978-1-4020-8116-3.
- ^ а б Harris, TE ; Росс, Ф.С. (1955). «Основы метода оценки чистой пропускной способности железных дорог» (PDF) . Меморандум об исследованиях .
- ^ а б Ford, LR ; Фулкерсон, Д.Р. (1956). «Максимальный поток через сеть». Канадский математический журнал . 8 : 399–404. DOI : 10,4153 / CJM-1956-045-5 .
- ^ a b Ford, LR, Jr .; Фулкерсон, Д. Р., Потоки в сетях , Издательство Принстонского университета (1962).
- ^ Шерман, Иона (2013). «Почти максимальные потоки за почти линейное время». Материалы 54-го ежегодного симпозиума IEEE по основам информатики . С. 263–269. arXiv : 1304.2077 . DOI : 10.1109 / FOCS.2013.36 . ISBN 978-0-7695-5135-7. S2CID 14681906 .
- ^ Kelner, JA; Lee, YT; Orecchia, L .; Сидфорд, А. (2014). «Алгоритм почти линейного времени для приближенного максимального потока в неориентированных графах и его многокомпонентные обобщения» (PDF) . Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 217. arXiv : 1304.2338 . DOI : 10.1137 / 1.9781611973402.16 . ISBN 978-1-61197-338-9. S2CID 10733914 . Архивировано из оригинального (PDF) 03 марта 2016 года.
- ^ Найт, Хелен (7 января 2014 г.). «Новый алгоритм может значительно упростить решение проблемы« максимального потока »» . MIT News . Проверено 8 января 2014 года .
- ^ а б Орлин, Джеймс Б. (2013). «Макс течет за время O (нм) или лучше». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . STOC '13 Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . С. 765–774. CiteSeerX 10.1.1.259.5759 . DOI : 10.1145 / 2488608.2488705 . ISBN 9781450320290. S2CID 207205207 .
- ^ Malhotra, VM; Кумар, М. Прамодх; Махешвари, С. Н. (1978). "An О ( | V | 3 ) {\ Displaystyle O (| V | ^ {3})} алгоритм поиска максимальных потоков в сетях » (PDF) . Письма об обработке информации . 7 (6): 277–278. doi : 10.1016 / 0020-0190 (78) 90016-9 .
- ^ а б в Гольдберг, А.В .; Tarjan, RE (1988). «Новый подход к проблеме максимального расхода» . Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 . S2CID 52152408 .
- ^ Cheriyan, J .; Махешвари, С. Н. (1988). «Анализ алгоритмов проталкивания предпотока для максимального сетевого потока». Основы программных технологий и теоретической информатики . Конспект лекций по информатике. 338 . С. 30–48. DOI : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4. ISSN 0302-9743 .
- ^ King, V .; Rao, S .; Тарджан, Р. (1994). «Более быстрый детерминированный алгоритм максимального потока». Журнал алгоритмов . 17 (3): 447–474. DOI : 10.1006 / jagm.1994.1044 . S2CID 15493 .
- ^ Гольдберг, А.В .; Рао, С. (1998). «За барьером разложения потока». Журнал ACM . 45 (5): 783. DOI : 10.1145 / 290179.290181 . S2CID 96030 .
- ^ Kathuria, T .; Лю, Ю.П .; Сидфорд, А. (16–19 ноября 2020 г.). Емкость агрегата Максимальный расход почтиВремя . Дарем, Северная Каролина, США: IEEE. С. 119–130.CS1 maint: формат даты ( ссылка )
- ^ Мадры, Александр (9–11 октября 2016 г.). Вычисление максимального расхода с увеличением электрических потоков . Нью-Брансуик, Нью-Джерси: IEEE. С. 593–602.CS1 maint: формат даты ( ссылка )
- ^ Brand, J. vd; Lee, YT; Nanongkai, D .; Peng, R .; Саранурак, Т .; Сидфорд, А .; Песня, З .; Ван, Д. (16–19 ноября 2020 г.). Двудольное сопоставление в почти линейное время на умеренно плотных графах . Дарем, Северная Каролина, США: IEEE. С. 919–930.CS1 maint: формат даты ( ссылка )
- ^ Brand, J. vd; Lee, YT; Лю, Ю.П .; Саранурак, Т .; Сидфорд, А; Песня, З .; Ван, Д. (2021). «Потоки с минимальной стоимостью, MDP и 1-регрессия в почти линейное время для плотных экземпляров». arXiv : 2101.05719 [ cs.DS ].
- ^ Gao, Y .; Лю, Ю.П .; Пэн, Р. (2021). «Полностью динамические электрические потоки: разреженный максимальный поток быстрее, чем у Гольдберга-Рао». arXiv : 2101.07233 [ cs.DS ].
- ^ Итаи, А .; Perl, Y .; Шилоач, Ю. (1982). «Сложность поиска максимальных непересекающихся путей с ограничениями длины». Сети . 12 (3): 277–286. DOI : 10.1002 / нетто.3230120306 . ISSN 1097-0037 .
- ^ Шварц, БЛ (1966). «Возможные победители частично завершенных турниров». SIAM Обзор . 8 (3): 302–308. Bibcode : 1966SIAMR ... 8..302S . DOI : 10.1137 / 1008062 . JSTOR 2028206 .
- ^ а б Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001). «26. Максимальный расход». Введение в алгоритмы, второе издание . MIT Press и McGraw-Hill. С. 643–668. ISBN 978-0-262-03293-3.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Карл Кингсфорд. «Удлинители максимального расхода: циркуляции с потребностями» (PDF) .
- ^ «Проект imagesegmentationwithmaxflow, содержащий исходный код для создания этих иллюстраций» . GitLab . Архивировано из оригинала на 2019-12-22 . Проверено 22 декабря 2019 .
- ^ «Дизайн алгоритмов» . www.pearson.com . Проверено 21 декабря 2019 .
- ^ Шауэр, Иоахим; Пферши, Ульрих (2013-07-01). «Задача о максимальном потоке с дизъюнктивными ограничениями». Журнал комбинаторной оптимизации . 26 (1): 109–119. CiteSeerX 10.1.1.414.4496 . DOI : 10.1007 / s10878-011-9438-7 . ISSN 1382-6905 . S2CID 6598669 .
дальнейшее чтение
- Джозеф Чериян и Курт Мельхорн (1999). «Анализ правила выбора наивысшего уровня в алгоритме preflow-push max-flow». Письма об обработке информации . 69 (5): 239–242. CiteSeerX 10.1.1.42.8563 . DOI : 10.1016 / S0020-0190 (99) 00019-8 .
- Дэниел Д. Слейтор и Роберт Э. Тарджан (1983). «Структура данных для динамических деревьев» (PDF) . Журнал компьютерных и системных наук . 26 (3): 362–391. DOI : 10.1016 / 0022-0000 (83) 90006-5 . ISSN 0022-0000 .
- Юджин Лоулер (2001). «4. Сетевые потоки». Комбинаторная оптимизация: сети и матроиды . Дувр. С. 109–177. ISBN 978-0-486-41453-9.