Сложность некоторых алгоритмических проблем для кососимметрических графов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Бабенко, Максим Александрович

• Бабенко, Максим Александрович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Бабенко, Максим Александрович

Введение

1. Основные определения, обозначения и свойства

1.1. Обозначения.

1.2. Потоки в сетях.

1.3. Декомпозиции потоков.

1.4. Минимаксные потоковые теоремы.

Введение диссертации (часть автореферата) на тему «Сложность некоторых алгоритмических проблем для кососимметрических графов»

3.2. Фрагменты, ростки и барьеры.32

3.3. Алгоритм поиска регулярного пути.34

3.4. Реализация алгоритма поиска регулярного пути.36

3.5. Консервативность и регулярная консервативность.38

3.6. Алгоритм поиска кратчайшего регулярного пути.41

3.7. Реализация алгоритма поиска кратчайшего регулярного пути.44

3.8. Случай произвольных длин дуг.50

4. Стоимостные потоки в кососимметрических сетях 53

4.1. Введение .53

4.2. Алгоритм дополнения вдоль путей минимальной стоимости.54

4.3. Алгоритм сведения к задаче в стандартной направленной сети.59

5. Ациклические кососимметрические графы 62

5.1. Введение .62

5.2. Ациклические графы.63

5.3. Регулярно ациклические графы.64

5.4. Приложение к теории паросочетаний.66

5.5. Ациклическая декомпозиция.67

5.6. Алгоритм проверки регулярной ацикличности. 67

5.7. Характеризация в терминах сильно связных компонент. 72

6. Задача о цикле минимального среднего веса 75

6.1. Введение . 75

6.2. Общий подход. 76

6.3. Минимальные средние регулярные циклы. 78

7. Потоки в простых кососимметрических сетях 81

7.1. Введение .81

7.2. Оценка мощности носителя ациклического потока.82

7.3. Оценка величины потока.86

7.4. Метод блокирующего потока.86

8. Декомпозиция многополюсных потоков 88

8.1. Введение . 88

8.2. Декомпозиция в направленных графах. 89

8.3. Декомпозиция в кососимметрических графах. 91

9. Мультипотоки в двунаправленных и кососимметрических сетях 94

9.1. Введение . 94

9.2. Мультипотоки в кососимметрических сетях. 97

9.3. Случай двух пар терминалов. 99

9.4. Случай трех пар терминалов.101

9.5. Общий случай.104

9.6. Оценка времени работы.105

Литература 108

Предметный указатель 112

Введение

Основные понятия

Данная работа относится к теории комбинаторной оптимизации. В качестве основного объекта рассмотрения выступают графы: стандартные (направленные и ненаправленные), а также нестандартные (кососимметрические и двунаправленные).

Приведем вначале основные определения, касающиеся двух стандартных типов графов: направленных и ненаправленных. Направленный граф G представляет собой четверку (V, A, tail, head), где V — конечное множество вершин, А — конечное множество дуг, а отображения tail: A-+V, head: А —» V сопоставляют каждой дуге а е А пару различных вершин: начало tail(a) и конец head(a). Если head(ai) = head(<22) и tail(ai) = tail(a2), то дуги а\ и аг называют параллельными. В случае когда не возникает неоднозначностей в понимании, дугу, идущую из вершины и в вершину v, мы будем обозначать через (u,v). Более того, при записи функций от дуг графа будем опускать двойные скобки и писать f(u,v) вместо полного варианта f((u,v)).

Маршрутом Р из s в t (или, для краткости, s-t маршрутом) в направленном графе G называют последовательность вершин и дуг вида

P=(s = vq, ах, vx,., vk-h ak, vk = t), где Vi — вершины (0 ^ i ^ k), а» — дуги, tail(aj) = V{-1, head(aj) = V{ (1 < г ^ k).

В случае если все дуги щ в последовательности Р различны, то маршрут Р будем называть простым по дугам (или путем); в случае если Vi ф Vj для всех 0 < i < j < k и vq ф Vi, vk ф Vi для всех 0 < г < к, то простым по вершинам (или простым путем). Отметим, что концы простого пути могут совпадать. Маршрут Р будем называть циклическим, если s = t; циклический маршрут, являющийся (простым) путем, будем называть (простым) циклом.

Переходим теперь к понятию ненаправленного графа. Каждый такой граф задается тройкой (V,E,ends), где V — конечное множество вершин, Е — конечное множество ребер, а отображение ends задает для каждого ребра ее Е множество ends(e) = состоящее из двух различных вершин и, v (концов е). В случае если ends(ei) = ends(e2), то ребра е\ и ег называют параллельными. Ребро, соединяющее вершины uviv, мы обозначаем через {и, v}.

Понятие маршрута переносится на случай ненаправленного графа следующим образом. Маршрутом Р из set (s-t маршрутом) в ненаправленном графе G называют последовательность вершин и ребер вида

Р ={vo,e1,v1,.,vk-hek,vk),

Рис. 1. Пример двунаправленного графа где Vi — вершины (0 < i ^ к), ei — ребра, ends(ej) = {«i-i,!;,-} (1 ^ г < к).

Если все ребра е* в последовательности Р различны, то маршрут Р будем называть простым по ребрам (или путем). Определения понятий простого по вершинам маршрута (или, иначе говоря, простого пути), циклического маршрута, а также цикла и простого цикла полностью повторяют соответствующие определения для случая направленного графа.

Понятие двунаправленного графа возникло в работах Эдмондса и Джонсона при решении специального класса задач целочисленного программирования [19, 35, 45]. Двунаправленный граф G — это четверка (V, Е, ends,со). Здесь V — конечное множество вершин, Е — конечное множество двунаправленных ребер. Отображение ends определено на множестве Е и сопоставляет каждому ребру е Е Е двухэлементное мультимножество ends(e) = {u,v}, где и, v — вершины (не обязательно различные), называемые концами е. Наконец, для каждого ребра е Е Е и вершины v Е ends(e) определено значение u(e,v) Е {+1,-1}, называемое направлением ребра е в вершине v. В случае если ш(е, v) = +1, то говорят, что ребро е входит в v, иначе говорят, что ребро е выходит из v. Отметим, что возможен случай ends(e) = {v, и}; такие ребра е называют двунаправленными петлями. В случае uj(e,v) = +1, петля е дважды входит в и; иначе е дважды выходит из v.

Итак, каждое ребро е Е Е соединяет две вершины и, v Е ends(e) и принадлежит к одному из следующих трех типов:

1) направленное ребро (или дуга), которое выходит из одного конца и заходит в другой (при этом и ф и);

2) ребро, входящее в оба конца;

3) ребро, выходящее из обоих концов.

Пример двунаправленного графа представлен на рис. 1.

Маршрут из s в t (s-t маршрут) в двунаправленном графе G представляет собой чередующуюся последовательность вершин и ребер где Vi — вершины (0 < г ^ k), ej — двунаправленные ребра, ends(ej) = {vi-\,vi} (1 ^ г ^ к), и для всех 0 < i < к ребра е*, ei+1 образуют транзитную пару в вершине Vi, то есть одно из ребер е*, e;+i входит в V{, а другое выходит из Uj.

1)

P=(s = v0, еь vi,., ек, vk = t),

Как и в случае обычных графов, маршрут без повторяющихся ребер называют путем. Понятие простого пути вводится для двунаправленных графов точно так же, как и для направленных и ненаправленных. Маршрут (1), в котором s = t, и ребра е\,ек образуют транзитную пару в вершине s, называют циклическим. Циклический маршрут, являющийся (простым) путем, называют (простым) циклом.

Направленный граф можно считать двунаправленным, превратив каждую дугу а = (u,v) исходного графа в ребро еа с множеством концов {u,v} и положив ш(еа>и) := —1, и>(еа,v) := +1. При этом семейство маршрутов исходного направленного графа и семейство маршрутов полученного двунаправленного графа находятся в естественном взаимно однозначном соответствии.

Для произвольного графа G мы будем писать Vg (соответственно Ас, Ее) для обозначения его множества вершин (соответственно дуг, ребер). Аналогично через Vp, Ар, Ер будут обозначаться мультимножества вершин, дуг и ребер произвольного маршрута Р.

Для двунаправленных графов существует также альтернативный и отчасти более удобный язык их описания — так называемые кососимметрические графы. Определение кососимметрического графа было сформулировано в работах Гольдберга и Карзанова [25, 26], а также Татта [48] (где они получили название антисимметрических орграфов). Рассмотрим направленный граф G. Пусть задана пара биекций ay: Vg —<► Vg и о а '■ Ag —* Ас, обладающих следующими свойствами:

1) оу(оу(г;)) = v для всех v eVg и <тл(сгд(а)) = а для всех о 6 Ас',

2) oy(v) ^ v для всех v eVc и стд(а) ф а для всех а G Ас',

3) Ьеас1(<7л(а)) = oy(tail(a)) и tail(cr^(a)) = 0y(head(a)) для всех a G Ас

Тогда тройку (G,ov,(?a) будем называть кососимметрическим графом. Если это не вызывает разночтений, мы будем называть кососимметрическим и сам направленный граф G. В дальнейшем нам потребуется работать как с кососимметрическими, так и с обычными направленными графами. Для того, чтобы подчеркнуть отсутствие кососимметрической структуры у последних, будем называть их стандартными.

Пару отображений (ау,<та) мы скомбинируем в одно отображение a: Vg U Ас * VgUAq. Отображения а, оу, о а будем называть отображениями симметрии графа. Для удобства записи мы будем использовать обозначение х' для образа а(х) (как по отношению к вершинам, так и к дугам). Элемент х' (вершину или дугу) будем называть симметричным к элементу х. Множество вершин Vg тогда разбивается на не пересекающиеся пары симметричных вершин; также дело обстоит и с множеством дуг. Симметрия естественным образом переносится на подмножества вершин и дуг графа. Из определения следует, что если в кососимметрическом графе G присутствуют дуги, соединяющие пару симметричных вершин v, г/, то таких дуг непременно четное число, и они разбиваются на пары симметричных.

Соответствие между двунаправленными и кососим-метрическими графами

Покажем теперь, как введенное понятие кососимметрического графа связано с понятием двунаправленного (см. также [26, раздел 2]). Пусть X — произвольное множество вершин двунаправленного графа G. Рассмотрим следующее преобразование: для всех вершин v G X и ребер е, инцидентных v, обратим направление ребра е в вершине v. Данное преобразование не меняет множества маршрутов в G. Мы будем называть двунаправленные графы G\, G2 эквивалентными, если G2 можно получить из G\, применяя вышеуказанное преобразование для некоторого множества X.

Пусть задан кососимметрический граф G. Выберем произвольное упорядоченное разбиение ж = (Vi, V2) множества Vq (то есть Va — Vi U V2, V\ П V2 = 0), такое что V{ = V2. Тогда по G и 7г можно построить двунаправленный граф G с множеством вершин V\ следующим способом: ребра G будут соответствовать парам симметричных дуг в G. Точнее, каждая пара симметричных дуг а, а' в G порождает одно ребро е в G, соединяющее вершины u,v Е V\, так что:

1) ребро е идет из и в и, если одна из дуг а, а' идет из и в г; (а другая из v' в и');

2) ребро е выходит из обоих концов и, v, если одна из дуг а, а' идет из и в и' (а другая из г; в и');

3) ребро е входит в оба конца и, v, если одна из дуг а, а' идет ю и' в v (а другая из v' в и).

В частности, ребро е будет петлей, если дуги а, а' соединяют пару симметричных вершин.

Обратно, двунаправленный граф G порождает кососимметрический граф G с отображением симметрии а следующим образом. Для каждой вершины v G Vq возьмем ее копию a(v) и образуем множество V~ := {а(и) \v EVg}. Положим Vq :=Vq U V~. Для каждого ребра е 6 Eg, соединяющего вершины иив, построим две симметричные дуги а, а' € Aq, чтобы выполнялись указанные выше условия 13. Пример соответствия между двунаправленными и кососимметрическими графами представлен на рис. 2.

Отметим, что каждый двунаправленный граф порождает один кососимметрический. В то же время, кососимметрический граф G порождает набор двунаправленных в зависимости от выбранного разбиения 7Г множества вершин, которое используется при построении G. Все получающиеся так графы G, однако, будут эквивалентны.

Существует также соответствие между маршрутами в G и маршрутами в G. А именно, пусть т обозначает отображение VgUAq на VgUEg,, склеивающее пары симметричных вершин и дуг. Каждый маршрут Р = (г^о, а\, V\,., a*, Vk) в G индуцирует последовательность т(Р) := (т(г> о), r(aj), t(vi), ., т(йк), т(г^)) вершин и ребер из G. Легко видеть, что т(Р) будет маршрутом в G.

В приложениях особенно важную роль играют не произвольные маршруты в графах, а пути. Если в направленном графе вершина t достижима из вершины s по

У1 а) Двунаправленный граф G б) Соответствующий кососим-метрический граф G

Рис. 2. Соответствие между двунаправленными и кососимметрическими графами некоторому маршруту, то t также достижима по некоторому пути (даже простому). В противоположность этому, в двунаправленном графе наличие s-t маршрута не влечет за собой наличие s-t пути. Проверка наличия s-t пути в двунаправленном графе, вообще говоря, представляет собой достаточно сложную задачу.

Будем называть маршрут нетривиальным, если он содержит хотя бы одно ребро (или дугу). Путь в кососимметрическом графе будем называть регулярным, если в нем не встречается пары симметричных дуг (при этом симметричные вершины встречаться могут). По каждому нетривиальному маршруту р = (wq,е\,w\,.,е*,wk) в графе G можно построить последовательность т(Р) := (vo,ai,vi,.,ak,Vk) из вершин и дуг графа G по следующему правилу:

1) если ребро t\ выходит из Wq (соответственно входит в Wq), то положим v0:=W0 (соответственно Vo := w'0);

2) для всех 1 ^ г ^ к если ребро е{ выходит из w^i, то в качестве щ возьмем дугу из множества т-1(е*), которая выходит из кроме того положим V{ :=

3) для всех 1 ^ i ^ к если ребро е; входит в Wj-i, то в качестве а* возьмем дугу из множества r1(ej), которая выходит из х; кроме того положим Vi := head(aj).

В случае когда ребро е* представляет собой петлю, то дуги из т-1(е*) оказываются параллельными, поэтому дуга щ выбирается из двух возможных произвольным образом. Несложно показать, что для любого нетривиального маршрута Р в G справедливы свойства:

1) т(Р) представляет собой маршрут в G, причем т(т(Р)) = Р\

2) Р представляет собой путь (то есть простой по ребрам маршрут), если и только если т (Q) представляет собой регулярный путь.

Тем самым, отображения т, т задают взаимно однозначное (с точностью до выбора представителя из пары параллельных дуг вида (v, v'), как указано выше) соответhead(aj); ствие между семействами нетривиальных маршрутов (соответственно нетривиальных путей) в G и нетривиальных маршрутов (соответственно нетривиальных регулярных путей) в G.

Как будет показано далее в главе 2, в терминах кососимметрических графов оказывается возможным описать широкий спектр задач комбинаторной оптимизации (паросочетания в графах общего вида, Т-соединения, ^паросочетания, /-факторы, упаковки Т-путей и другие). Тем самым, теория кососимметрических графов служит удобным обобщающим инструментом, а алгоритмы для задач на кососимметрических графах находят множество применений.

Основную часть работы составляют главы 3-9. Рассматриваемые в них задачи могут быть разделены на следующие три класса.

Первый класс составляют задачи, связанные с разысканием в кососимметри-ческом графе G кратчайшего регулярного пути между выбранной парой вершин. Длины дуг могут быть произвольными (в том числе отрицательными) числами, а длиной пути называется сумма длин составляющих его дуг. При этом предполагается, что длины симметричных дуг равны, и в графе отсутствуют регулярные циклы отрицательной длины. В работе Гольдберга и Карзанова [25] представлен алгоритм с оценкой О (тп2 log п). (Здесь и далее через п обозначается число вершин графа, а через т — число ребер или дуг. При этом предполагается, что 2п ^ т ^ п2). Мы улучшаем данную оценку до 0(min(mnlogn, п3)). Этому вопросу будет посвящена глава 3.

Второй класс образуют задачи, связанные с циклической структурой кососимметрических и двунаправленных графов. Мы обобщаем понятие ацикличности на случай кососимметрических графов. При этом оно распадается на два: обычная ацикличность (отсутствие циклов) и регулярная ацикличность (отсутствие регулярных циклов). В главе 5 для каждого из этих типов мы устанавливаем структурные результаты, а также предъявляем алгоритмы, позволяющие выполнить проверку на принадлежность данного графа к указанному типу за линейное время. Структурные результаты для случая регулярной ацикличности позволяют дать короткое доказательство известной в теории паросочетаний теоремы Коцига [34] (утверждающей, что если в ненаправленном графе G существует и единственно совершенное паросо-четание М, то в G есть мост, причем М содержит хотя бы один из мостов G).

Среди проблем второго класса следует также упомянуть задачу о разыскании в кососимметрическом графе G регулярного цикла минимального среднего веса. (Предполагается, что дугам графа приписаны вещественные веса, при этом веса симметричных дуг равны. Под средним весом цикла понимается отношение суммы весов его дуг к их количеству.) Для стандартных направленных графов эта задача изучалась Карпом [32] (алгоритм с оценкой 0(тп)), а для ненаправленных — Барахоной [16] (алгоритм с оценкой 0(min(m2nlogn, тп3))). Задача на кососимметрическом графе обобщает обе упомянутые проблемы и, как мы показываем в главе 6, может быть решена за время 0(min(mn2logn,n4)). В частности, мы улучшаем оценку Барахоны.

Третий класс складывается из потоковых и мультипотоковых задач. В главе 4 рассматривается проблема нахождения в кососимметрических сетях целочисленных кососимметрических потоков минимальной стоимости; для ее решения предлагается два алгоритма. Оценка сложности первого составляет 0(kmm(m\ogn,п2)), где к — величина потока. Второй алгоритм имеет оценку сложности 0(ф(п, т) + min(mnlogn, п3)), где ф(п', т!) обозначает сложность задачи о целочисленной циркуляции минимальной стоимости в стандартной направленной сети с п' вершинами и т' дугами.

В главе 7 мы изучаем случай простых кососимметрических сетей, то есть косо-симметрических графов, в которых каждой дуге приписана единичная пропускная способность, и параллельные дуги отсутствуют. Для стандартного направленного случая потоковая задача в простых сетях изучалась Карзановым, Эвеном, Таржа-ном [б, 20]. Был получен алгоритм со временем работы 0(vmn(mn2^, тп3/2)). Для двунаправленных сетей оценка сложности 0(т3/2) была получена Габовым [22]. В наших построениях мы опираемся на разработанный ранее Гольдбергом и Карзановым [26] метод блокирующих потоков в кососимметрических сетях. Мы устанавливаем для данного метода оценку сложности 0(тп2//3), тем самым полностью ликвидируя зазор между стандартным и кососимметрическим вариантами задачи. Ключевую роль играет доказываемое нами утверждение о том, что всякий ациклический целочисленный кососимметрический поток в кососимметрической сети без параллельных дуг имеет носитель размера 0{rty/v), где v — величина потока (аналог этого утверждения для стандартных направленных сетей был получен Каргером и Левиным [33]).

В главе 8 изучается вопрос о построении в стандартной направленной сети разложения многополюсного потока на слагаемые, отвечающие всевозможным парам источников и стоков. Предлагаемый алгоритм имеет оценку сложности 0(m\og(n2/т)) (в предположении, что число источников и стоков ограничено константой). Также рассматривается обобщение на случай кососимметрических сетей.

В главе 9 изучаются целочисленные мультипотоковые задачи в кососимметрических сетях. В общей постановке эти проблемы являются NP-трудными, поэтому мы ограничиваемся классом внутренне сбалансированных сетей (то есть таких, в которых для любой внутренней вершины v суммы пропускных способностей дуг, входящих вии выходящих из v, равны). Ранее задача о максимальном мультипо-токе изучалась для случая ненаправленных и стандартных направленных сетей в работе Ибараки, Карзанова, Нагамочи [31]. Кососимметрический случай является одновременным обобщением как направленного, так и ненаправленного. Мы излагаем алгоритм для нахождения искомого целочисленного кососимметрического муль-типотока за время 0(mnlog(n2/m)\ogt) (где t обозначает количество терминалов). Эта оценка совпадает со временем работы известного алгоритма для направленного случая и улучшает другую известную оценку 0(тп2) для ненаправленного случая.

Благодарности

Данная работа выполнена при поддержке грантов РФФИ № 03-01-00475, 05-0102803, 06-01-00122 и НШ 358.2003.1.

Автор выражает глубокую признательность доктору физико-математических наук, главному научному сотруднику Александру Викторовичу Карзанову за постановку задач, подробные обсуждения и множество полезных идей. Автор благодарен научному руководителю доктору физико-математических наук, профессору Николаю Константиновичу Верещагину за постоянное внимание к работе.

Автор признателен профессору Владимиру Андреевичу Успенскому, профессору Мати Рейновичу Пентусу, а также кандидату физико-математических наук Александру Шеню за конструктивные предложения, высказанные ими во время докладов автора на семинарах кафедры математической логики и теории алгоритмов.

Автор глубоко благодарит своих родителей, Бабенко Александра Максимовича и Кашенкову Валентину Сергеевну за поддержку, оказанную во время написания работы.

Список литературы диссертационного исследования кандидат физико-математических наук Бабенко, Максим Александрович, 2007 год

1. Карзанов А. В. Алгоритм максимальной упаковки нечетнополюсных разрезов и его приложения // Сб.: Исследования по прикладной теории графов. Новосибирск: Наука СО. 1986. С. 126-140.

2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

3. Черкасский В. В. Решение задачи о многопродуктовом потоке в сети // Сб.: Экономика и математические методы. 1977. Т. 13, № 1. С. 143-151.

4. AhujaR. К., Goldberg A. V., OrlinJ. В., TarjanR. E. Finding Minimum-Cost Flows by Double Scaling // Mathematical Programming. 1992. V. 53, № 3. P. 243-266.

5. Anstee R. P. An Algorithmic Proof of Tutte's F-Factor Theorem // Journal of Algorithms. 1985. V. 6, № 1. P. 112-131.

6. Anstee R. P. A Polynomial Algorithm for B-Matchings: an Alternative Approach // Information Processing Letters 1987. V. 24, № 3. P. 153-157.

7. Babenko M. A. Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure // Lecture Notes in Computer Science. 2006. V. 3967. P. 23-34.

8. Barahona F. Reducing Matching to Polynomial Size Linear Programming // SIAM Journal on Optimization. 1993. V. 3. P. 688-695.

9. Bouchet A. Isotropic Systems // European Journal of Combinatorics. 1987. V. 8. P. 231-244.

10. Bouchet A. Matchings and Delta-Matroids // Discrete Applied Mathematics. 1989. V. 24, № 16. P. 55-62.

11. Edmonds J., Johnson E. L. Matching, a Well-Solved Class of Integer Linear Programs // Combinatorial Structures and Their Applications, Calgary International Conference. NY: Gordon and Breach, 1970. P. 89-92.

12. Even S., Tarjan R. E. Network Flow and Testing Graph Connectivity 11 SIAM Journal on Computing. 1975. V. 4. P. 507-518.

13. Ford L., Fulkerson D. Flows in Networds. Princeton: Princeton University Press, 1962.

14. Gabow H. N. An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems // Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. 1983. V. 15. P. 448-456.

15. Gabow H. N., Kaplan H., Tarjan R. E. Unique Maximum Matching Algorithms // Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing. 1999. P. 70-78.

16. Gabow H. N., Tarjan R. E. A Linear-Time Algorithm for a Special Case of Disjoint Set Union // Journal of Computer and System Sciences. 1986. V. 30. P. 209-221.

17. Goldberg A. V., Karzanov A. V. Path Problems in Skew-Symmetric Graphs // Combinatorics 1996. V. 16, № 3. P. 353-382.

18. Goldberg A. V., Karzanov A. V. Maximum Skew-Symmetric Flows and Matchings // Mathematical Programming. 2004. V. 100, № 3. P. 537-568.

19. Goldberg A., Tarjan R. Solving Minimum-Cost Flow Problems by Successive Approximation // Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing. NY: ACM Press, 1987. P. 7-18.

20. Goldberg A. V., Tarjan R. E. A New Approach to the Maximum-Flow Problem // Journal of ACM. 1988. V. 35, № 4. P. 921-940.

21. Goldberg A. V., Tarjan R. Е. Finding Minimum-Cost Circulations by Canceling Negative Cycles // Journal of ACM. 1989. V. 36, № 4. P. 873-886.

22. Goldberg A. V., Rao S. Beyond the Flow Decomposition Barrier // Journal of ACM. 1998. V. 45, № 5. P. 783-797.

23. Ibaraki Т., Karzanov A. V., Nagamochi H. A Fast Algorithm for Finding a Maximum Free Multiflow in an Inner Eulerian Network and Some Generalizations // Combinatorica. 1998. V. 18, № 1. P. 61-83.

24. Karp R. M. A Characterization of the Minimum Cycle Mean in a Digraph // Discrete Mathematics. 1978. V. 23. P. 309-311.

25. Karger D. R., Levine M. S. Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching // Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. NY: ACM Press, 1998. P. 69-78.

26. Kotzig A. On the Theory of Finite Graphs with a Linear Factor I // Mat.-Fyz. Casopis Slovensk. Akad. Vied. 1959. V. 9. P. 73-91.

27. Lawler E. L. Combinatorial Optimization: Networks and Matroids. NY: Holt, Rein-hart, and Winston, 1976.

28. Lomonosov M. V. Combinatorial Approaches to Multiflow Problems // Discrete Applied Mathematics. 1985. V. 11, № 1. P. 1-94.

29. Lovasz L. On Some Connectivity Properties of Eulerian Graphs // Acta Math. Akad. Sci. Hung. 1976. V. 28. P. 129-138.

30. Lovasz L. Matroid Matching and Some Applications // Journal of Combinatorial Theory, Series B. 1980. V. 28. P. 208-236.

31. Lovasz L. Selecting Independent Lines from a Family of Lines in a Space // Acta Scientiarum Mathematicarum (Szeged). 1980. V. 42, № 1-2. P. 121-131.

32. Lovasz L. The Matroid Matching Problem // Colloq. Math. Society. Janos Bolyai. 1981. V. 25. P. 495-517.

33. Jloeac JI., Пламмер M. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

34. Mader W. Uber die Maximalzahl Kantendisjunkter A-Wege // Archiv der Mathe-matik (Basel). 1978. V. 30. P. 325-336.

35. Orlin J. A Faster Strongly Polynomial Minimum Cost Flow Algorithm // Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. NY: ACM Press, 1988. P. 377-387.

36. Oxley J. G. Matroid Theory. Oxford: Oxford University Press, 1992.

37. Schrijver A. Combinatorial Optimization. Berlin: Springer, 2003.

38. Sleator D. D., Tarjan R. E. A Data Structure for Dynamic Trees // Journal of Computer and System Sciences. 1983. V. 26, № 3. P. 362-391.

39. Tong P., Lawler E., Vazirani V. Solving the Weighted Parity Problem for Gammoids by Reduction to Graphic Matching // Progress in Combinatorial Optimization. 1982. P. 363-374.

40. Tutte W. T. Antisymmetrical Digraphs // Canadian Journal of Mathematics. 1967. V. 19. P. 1101-1117.

41. Whitney H. On the Abstract Properties of Linear Dependence // American Journal of Mathematics. 1935. V. 57. P. 509-533.Предметный указатель