Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Ссылки, использованные в пятой части
|
|
В публикациях, указанных ниже, содержатся описания большей части фундаментальных алгоритмов, которые мы изучали в главах 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.