Graph algorithms

Cover......Page 1
Graph Algorithms, 2nd Edition......Page 2
Title......Page 3
Copyright......Page 4
Contents......Page 5
Foreword......Page 7
Preface to the Second Edition......Page 8
Preface to the First  Edition......Page 10
1.1 Introduction to Graph Theory......Page 12
1.2 Computer Representation of Graphs......Page 14
1.3 Euler Graphs......Page 17
1.4 De Bruijn Sequences......Page 20
1.5.1 Breadth-First Search......Page 22
1.5.2 Dijkstra's Algorithm......Page 25
1.5.3 The Ford Algorithm......Page 28
1.5.4 The Floyd Algorithm......Page 32
1.6 Problems......Page 33
Bibliography......Page 39
2.1 Tree Definitions......Page 40
2.2 Minimum Spanning Tree......Page 42
2.3 Cayley's Theorem......Page 45
2.4 Directed Tree Definitions......Page 48
2.5 The Infinity Lemma......Page 50
2.6 Problems......Page 53
Bibliography......Page 55
3.1.1 Trémaux's Algorithm......Page 57
3.1.2 The Hopcroft-Tarjan Version of DFS......Page 60
3.2 Algorithm for Nonseparable Components......Page 63
3.3 DFS on Directed Graphs......Page 68
3.4 Strongly Connected Components of a Digraph......Page 69
3.5 Problems......Page 73
Bibliography......Page 75
4.1 Uniquely Decipherable Codes......Page 76
4.2 Positional Trees and Huffman's Optimization Problem......Page 80
4.3 Application of the Huffman Tree to Sort-by-Merge Techniques......Page 86
4.4 Catalan Numbers......Page 88
4.5 Problems......Page 93
Bibliography......Page 94
5.1 Introduction......Page 96
5.2 The Algorithm of Ford and Fulkerson......Page 98
5.3 The Dinitz Algorithm......Page 105
5.4 Networks with Upper and Lower Bounds......Page 113
5.5 Problems......Page 120
Bibliography......Page 126
6.1 Zero-One Network Flow......Page 128
6.2 Vertex Connectivity of Graphs......Page 132
6.3 Connectivity of Digraphs and Edge Connectivity......Page 140
6.4 Maximum Matching in Bipartite Graphs......Page 146
6.5 Two Problems on PERT Digraphs......Page 148
6.6 Problems......Page 152
Bibliography......Page 156
7.1 Bridges and Kuratowski's Theorem......Page 157
7.2 Equivalence......Page 168
7.3 Euler's Theorem......Page 169
7.4 Duality......Page 170
7.5 Problems......Page 175
Bibliography......Page 178
8.1 Introduction......Page 179
8.2 The Path Addition Algorithm of Hopcroft and Tarjan......Page 180
8.3 Computing an st-Numbering......Page 188
8.4 The Vertex Addition Algorithm of Lempel, Even, and Cederbaum......Page 190
8.5 Problems......Page 196
Bibliography......Page 197
Index......Page 198