65707

Автор(ы): 

Автор(ов): 

3

Обложка: 

Параметры публикации

Тип публикации: 

Книга (брошюра, монография, стандарт)

Название: 

Потоковые алгоритмы

Сведения об издании: 

Сведения об издании: 

1-ое издание

ISBN/ISSN: 

-

Город: 

  • Москва

Издательство: 

  • Издательство "Наука"

Год издания: 

1975

Объём, стр.: 

120
Аннотация
Книга посвящена алгоритмам решения задачи о максимальном потоке в сети и ее обобщений на случай минимизации стоимости потока и на случай потоков нескольких продуктов в одной сети. Классические результаты в этой области — принципиальное решение некоторых основных задач — изложены в известной книге Л. Р. Форда и Д. Р. Фалкерсона «Потоки в сетях» - В книге «Потоковые алгоритмы» применен современный подход, когда алгоритмы оцениваются с точки зрения их эффективности. В книге описан ряд общих алгоритмов, построенных в последние годы в СССР и за рубежом, которые имеют наилучшие в настоящее время оценки трудоемкости. Показано, что некоторые важные комбинаторные задачи, сводящиеся к потоковым задачам, решаются этими алгоритмами более эффективно, чем известными ранее алгоритмами. Проводятся исследования эффективности и взаимной сводимости известных алгоритмов решения транспортной задачи. Приведены примеры, доказывающие экспоненциальную сложность этих алгоритмов. Доказана универсальность в классе задач линейного программирования одного варианта многопродуктовой потоковой задачи. Изложение книги построено так, чтобы дать представление об общей технике построения экономных алгоритмов.

Библиографическая ссылка: 

Адельсон-вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. М.: Издательство "Наука", 1975. – 120 с.