Алгоритм Гопкрофта-Карпа: различия между версиями

[непроверенная версия]

Версия 22:45, 11 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Гопкрофта-Карпа^[1] предназначен для решения задачи о назначениях в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время [math]O(m \sqrt{n})[/math].

1.2 Математическое описание

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

Java: JGraphT (класс HopcroftKarpBipartiteMatching).

3 Литература

↑ Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.

[1] Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.

[1]

@@ Строка 21: / Строка 21: @@
 === Выводы для классов архитектур ===
 === Существующие реализации алгоритма ===
+* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/HopcroftKarpBipartiteMatching.html HopcroftKarpBipartiteMatching]</code>).
 == Литература ==
 <references />