Data structures and network algorithms

Robert Endre Tarjan9780898711875, 0898711878

There has been an explosive growth in the field of combinatorial algorithms. These algorithms depend not only on results in combinatorics and especially in graph theory, but also on the development of new data structures and new techniques for analyzing algorithms.
Four classical problems in network optimization are covered in detail, including a development of the data structures they use and an analysis of their running time.
Data Structures and Network Algorithms attempts to provide the reader with both a practical understanding of the algorithms, described to facilitate their easy implementation, and an appreciation of the depth and beauty of the field of graph algorithms.
Adopted for classroom use by Harvard University, Dartmouth University, the University of Chicago, the University of Colorado, Brown University, the University of Pennsylvania, Johns Hopkins University, and Princeton University (partial listing).

---

Table of contents :
Data Structures and Network Algorithms……Page 1
Contents……Page 7
Preface……Page 9
CHAPTER 1 Foundations……Page 11
CHAPTER 2 Disjoint Sets……Page 33
CHAPTER 3 Heaps……Page 43
CHAPTER 4 Search Trees……Page 55
CHAPTER 5 Linking and Cutting Trees……Page 69
CHAPTER 6 Minimum Spanning Trees……Page 81
CHAPTER 7 Shortest Paths……Page 95
CHAPTER 8 Network Flows……Page 107
CHAPTER 9 Matchings……Page 123
References……Page 135