Вклад участника
17 января 2012
Алгоритм поиска блокирующего потока в ациклической сети
Малхотры — Кумара — Махешвари
+17
Алгоритм поиска блокирующего потока в ациклической сети
Алгоритм узкого места
+18
Эквивалентность состояний ДКА
Нет описания правки
-25
Автоматы с eps-переходами. Eps-замыкание
Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание
+1
Автоматы с eps-переходами. Eps-замыкание
Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание
+1
Построение по НКА эквивалентного ДКА, алгоритм Томпсона
Доказательство эквивалентности
+1
Использование обхода в глубину для топологической сортировки
Постановка задачи
-12
Обход в глубину, цвета вершин
Реализация
-131
Регулярные языки: два определения и их эквивалентность
Литература
-348
Регулярные языки: два определения и их эквивалентность
Нет описания правки
-11
Использование обхода в глубину для поиска компонент сильной связности
Доказательство корректности алгоритма
-110
Использование обхода в глубину для поиска компонент сильной связности
Доказательство корректности алгоритма
+53
Двудольные графы и раскраска в 2 цвета
Нет описания правки
Доказательство нерегулярности языков: лемма о разрастании
Литература
-27
Алгоритм Джонсона
Нет описания правки
-92
Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
Литература
-20
Алгоритм Джонсона
Нет описания правки
+1034
Детерминированные конечные автоматы
Литература
-10
Недетерминированные конечные автоматы
Литература
-26
Произвольно вычерчиваемые из заданной вершины графы
Нет описания правки
+106
Детерминированные конечные автоматы
Литература
-2
Произвольно вычерчиваемые из заданной вершины графы
Нет описания правки
+220
Детерминированные конечные автоматы
Нет описания правки
-17
Схема алгоритма Диница
Асимптотика алгоритма
-7
Обход в ширину
Нет описания правки
-28
Алгоритм Флойда
Нет описания правки
+101
Отношение рёберной двусвязности
См. также
+1
Отношение рёберной двусвязности
Реберная двусвязность
+33
Алгоритм Куна для поиска максимального паросочетания
Нет описания правки
+491
Отношение рёберной двусвязности
Реберная двусвязность
Алгоритм Куна для поиска максимального паросочетания
Релизация
+2
Отношение связности, компоненты связности
Источники
+82
Отношение рёберной двусвязности
Реберная двусвязность
+32
Алгоритм Куна для поиска максимального паросочетания
Алгоритм
+69
Отношение рёберной двусвязности
Реберная двусвязность
-2
Отношение рёберной двусвязности
Нет описания правки
-176
Отношение рёберной двусвязности
См. также
+1
Отношение рёберной двусвязности
См. также
+154
Отношение рёберной двусвязности
Реберная двусвязность
-1
Отношение рёберной двусвязности
Реберная двусвязность
+1
Отношение рёберной двусвязности
Реберная двусвязность
-40
Отношение рёберной двусвязности
Реберная двусвязность
-20
Отношение рёберной двусвязности
Нет описания правки
+708
Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Идея
+4
Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Идея
+221
Формула Уитни
Нет описания правки
+303
Матрица Татта и связь с размером максимального паросочетания в двудольном графе
Матрица Эдмондса
+9
Сведение задачи о назначениях к задаче о потоке минимальной стоимости
Нет описания правки
+70
Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
Нет описания правки
+97
Матрица Татта и связь с размером максимального паросочетания в двудольном графе
Матрица Татта
-267