Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Ссылки, использованные в пятой части




В публикациях, указанных ниже, содержатся описания большей части фундаменталь­ных алгоритмов, которые мы изучали в главах 17-21. Эти книги являются основными справочными пособиями, которые содержат подробный анализ фундаментальных и со­временных алгоритмов на графах, изобилующих пространными ссылками на. современ­ную литературу. В книге Ивена (Even) и монографии Тарьяна (Tarjan) подробно рассмат­риваются многое из того, что изучалось в этой книге. Оригинальная статья Тарьяна, в которой рассматриваются вопросы применения поиска в глубину для решения задач о связности и ряд других задач, заслуживает дальнейшего изучения, Описанная в главе 19 реализация топологической сортировки на базе очереди истоков взято из книги Кнута (Knuth). Ссылки на источники описаний других специальных алгоритмов, которые мы рассматривали в этой книге, приводятся ниже.

Алгоритмы построения минимальных остовных деревьев в насыщенных графах, ко­торые мы изучали в главе 20, известны давно, однако пионерские статьи Дейкстры (Dijkstra), Прима (Prim) и Крускала (Kruskal) и сегодня заслуживают внимания. В обзо­ре, написанном Грэхемом (Graham) и Хеллом (Hell), подробно изложена занимательная история этой задачи. Статья Чейзела (Chazelle) описывает современное положение дел в поиске линейного алгоритма построения минимальных остовных деревьев.

Книга, написанная Ахуджа (Ahuja), Маньянти (Magnanti) и Орлином (Orlin) представ­ляет собой всестороннее исследование алгоритмов вычисления потоков в сетях (и алго­ритмов построения кратчайших путей). В этой книге вы найдете дополнительную инфор­мацию, касающуюся фактически каждой темы, рассмотренной в главах 21 и 22. Другим источником дальнейших материалов по этой теме может послужить классический труд Пападимитриу (Papadiminriou) и Стейлица (Steiglitz). Несмотря на то что в этой книге, главным образом, рассматриваются более сложные вопросы, в ней вы найдете подроб­ное описание многих алгоритмов, изучаемых в данной книге. Обе книги содержат мно­гочисленные и подробные ссылки на источники в научно-исследовательской литературе. Классическая работа Форда (Ford) и Фалкерсона (Fulkerson) все еще заслуживает изу­чения, поскольку в ней впервые вводятся многие фундаментальные понятия.

В этой книге мы кратко коснулись многих актуальных тем, которые подробно рас­сматриваются в части 8 (которая очень скоро увидит свет), в том числе вопросы своди­мости, трудной разрешимости и линейного программирования. Предлагаемый здесь спи­сок публикаций охватывает материал, с которым мы здесь подробно ознакомились, и который, тем не менее, не дает полного представления об этой современной тематике. Многое можно почерпнуть из текстов алгоритмов, а книга Пападимитриу и Стейлица послужит прекрасным введением. Этим темам посвящено множество других книг и об­ширная научно-исследовательская литература.





Часть 5. Алгоритмы на графах


R. К. Ahuja, Т. LMagnanti, and J. В. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

B. Chazelle, "A minimum spanning tree algorithm with inverse-Ackermann type complexity,"
Journal of the ACM, 47 (2000).

T. H. Cormen, C. L. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik,

1 (1959).

P. Erd.os and A. Renyi, "On the evolution of random graphs," Magyar Tud. Akad. Mat Kutato Int KozU 5 (1960).

S. Even, Graph Algorithms, Computer Science Press, 1979.

L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.

H. N. Gabow, "Path-based depth-first search for strong and biconnected components," Information Processing Letters, 74 (2000).

R. L. Graham and P. Hell, "On the history of the minimum spanning tree problem," Annals of the History of Computing, 7 (1985).

D. B. Johnson, "Efficient shortest path algorithms," Journal of the ACM, 24 (1977).

D. E. Knuth, The Art of Computer Programming. Volume I: Fundamental Algorithms, third edition, Addison-Wesley, 1997.

J. R, Kruskal Jr., "On the shortest spanning subtree of a graph and the traveling salesman problem," Proceedings AMS, 7, 1 (1956).



K. Mehlhorn, Data Structures and Algorithms 2. NP-Completeness and Graph Algorithms, Springer-Verlag, 1984.

C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
Prentice-Hall, 1982.

R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, 36 (1957).

R. E. Tarjan, "Depth-first search and linear graph algorithms," SIAM Journal on Computing, 1,

2 (1972).

R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.



mylektsii.ru - Мои Лекции - 2015-2019 год. (0.023 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал