Data Structures and Network Algorithms by R.E.Tarjan, 1983, Bell Laboratories.

Contents

Preface vii
Chapter 1
FOUNDATIONS
1.1. Introduction 1
1.2. Computational complexity 2
1.3. Primitive data structures 7
1.4. Algorithmic notation 12
1.5. Trees and graphs 14
Chapter 2
DISJOINT SETS
2.1. Disjoint sets and compressed trees 23
2.2. An amortized upper bound for path compression 24
2.3. Remarks 29
Chapter 3
HEAPS
3.1. Heaps and heap-ordered trees 33
3.2. Cheaps 34
3.3. Leftist heaps 38
3.4. Remarks 42
Chapter 4
SEARCH TREES
4.1. Sorted sets and binary search trees 45
4.2. Balanced binary trees 48
4.3. Self-adjusting binary trees 53
Chapter 5
LINKING AND CUTTING TREES
5.1. Theproblemof linking and cutting trees 59
5.2. Representing trees as sets of paths 60
5.3. Representing paths as binary trees 64
5.4. Remarks 70
Chapter 6
MINIMUM SPANNING TREES
6.1. The greedy method 71
6.2. Three classical algorithms 72
6.3. The round robin algorithm 77
6.4. Remarks 81
Chapter 7
SHORTEST PATHS
7.1. Shortest-path trees and labeling and scanning 85
7.2. Efficient scanning orders 89
7.3. All pairs 94
Chapter 8
NETWORK FLOWS
8.1. Flows, cuts, and augmenting paths 97
8.2. Augmenting by blocking flows 102
8.3. Finding blocking flows 104
8.4. Minimum cost flows 108
Chapter 9
MATCH INGS
9.1. Bipartite matchings and network flows 113
9.2. Alternating paths 114
9.3. Blossoms 115
9.4. Algorithms for nonbipartite matching 119
References 125