Йенсен П., Барнес Д. Потоковое программирование (1984)

Потоки в сетях.
Введение.
Взаимосвязь между задачами потокового программирования.
Специальные случаи стандартной линейной задачи о потоке минимальной
стоимости.
Сети с выигрышами.
Предварительное знакомство с предметом, изучаемым в книге.
Историческая справка.
Упражнения.
Примеры моделей потокового программирования.
Введение.
Свободный узел и его параметры.
Стандартная линейная задача о потоке минимальной стоимости (примеры).
Транспортная задача (примеры).
Задача о назначениях (примеры).
Задача о кратчайшем пути (примеры).
Задача о максимальном потоке (примеры).
Сети с выигрышами (примеры).
Историческая справка.
Упражнения.
Формальные постановки задач потокового программирования .
Система обозначений в потоковых задачах.
Два полезных преобразования.
Алгебраическая модель сети.
Стандартная задача о потоке минимальной стоимости как задаче линейного программирования.
Основные понятия из теории графов.
Расширенные и предельные сети.
Сети с нелинейными функциями стоимости дуг.
Методы решения стандартной задачи о потоке минимальной стоимости.
Границы использования потоковых моделей.
Историческая справка.
Упражнения.
Алгоритмы подготовки, обработки и преобразования данных для потоковых задач.
Вычислительные затраты.
Представление сети.
Способ описания алгоритмов.
Ввод и хранение информации о сети.
Представление дерева.
Эквивалентные алгоритмы, в которых используется список прямого обхода дерева.
Алгоритмы изменения потока.
Историческая справка.
Упражнения.
Задача о кратчайшем пути.
Введение.
Поиск кратчайшего пути как задача о потоке минимальной стоимости.
Допустимые дуги с положительной стоимостью.
Сеть без отрицательных циклов.
Отрицательные циклы.
Алгоритм, в котором не используется базисное дерево.
Двойственный алгоритм поиска кратчайшего пути.
Историческая справка.
Практические упражнения.
Теоретические упражнения.
Задача о максимальном потоке.
Постановка задачи.
Содержательная интерпретация двойственной задачи.
Результаты теоретических исследований.
Базисные и небазисные алгоритмы.
Алгоритмы увеличения потока.
Историческая справка.
Практические упражнения.
Теоретические упражнения.
Стандартные задачи о потоке минимальной стоимости.
Метод максимального потока (MAXFLOW) для получения исходного допустимого решения прямой задачи.
Метод фиктивных дуг для получения допустимого начального решения прямой задачи.
Прямой небазисный алгоритм.
Прямой базисный алгоритм.
Двойственный алгоритм уменьшения невязок в узлах.
Историческая справка.
Упражнения.
Алгоритм исключения дефектов.
Модель сети.
Задача линейного программирования.
Состояния с дефектом.
Изменение потока.
Изменение потенциалов узлов.
Пример использования АИД.
Историческая справка.
Упражнения.
Методы преобразования сетей для обобщенных потоковых задач.
Введение.
Модель сети с выигрышами.
Модель линейного программирования.
Двойственная линейная задача.
Представление базиса.
Потоки в обобщенных сетях.
Потенциалы узлов.
Историческая справка.
Упражнения.
Обобщенные задачи о потоке минимальной стоимости.
Обобщенная задача о кратчайшем пути.
Все дуговые стоимости положительны, а все выигрыши дуг меньше единицы или равны единице.
Дуги с отрицательной стоимостью и выигрышами больше единицы.
Двойственный алгоритм решения задачи о кратчайшем пути.
Алгоритмы решения обобщенной задачи о потоке минимальной стоимости.
Метод аргментальных цепей.
Прямой метод.
историческая справка.
Упражнения.
Выпуклая задача о потоке минимальной стоимости.
Выпуклые функции стоимости.
Свойства решений.
Потоковые задачи в физических сетях.
Функция стоимости, зависящая от случайных переменных.
Кусочно-линейная аппроксимация.
Неявная кусочно-линейная аппроксимация.
Историческая справка.
Упражнения.
Вогнутые функции стоимости.
Области применения.
Некоторые обозначения.
Полный перебор.
Неполный перебор.
Нижняя оценка.
Алгоритм неполного перебора.
Пример.
Историческая справка.
Упражнения.
Список литературы.