Data structures and network algorithms. (English) Zbl 0584.68077

CBMS-NSF Regional Conference Series in Applied Mathematics 44. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-187-8). viii, 131 p. (1983).
In the last fifteen years there has been an explosive growth in the field of combinatorial algorithms. Although much of the recent work is theoretical in nature, many newly discovered algorithms are quite practical. These algorithms depend not only on new results in combinatorics and especially in graph theory, but also on the development of new data structures and new techniques for analyzing algorithms. My purpose is to reveal the interplay of these areas by explaining the most efficient known algorithms for a selection of combinatorial problems. The book covers four classical problems in network optimization, including a development of the data structures they use and an analysis of their running times. This material will be included in a more comprehensive two-volume work I am planning on data structures and graph algorithms.


68R10 Graph theory (including graph drawing) in computer science
90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity
90C35 Programming involving graphs or networks
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)