Algorithmic Graph Theory

PREFACE vii
1 INTRODUCTION TO GRAPH THEORY 1
1-1 Basic Concepts 1
1-2 Representations 8
1-2-1 Static Representations, 9
1-2-2 Dynamic Representations, 11
1-3 Bipartite Graphs 14
1-4 Regular Graphs 17
1-5 Maximum Matching Algorithms 19
1-5-1 Maximum Flow Method (Bigraphs), 19
1-5-2 Alternating Path Method (Bigraphs), 20
1-5-3 Integer Programming Method, 27
1-5-4 Probabilistic Method, 28
1-6 Planar Graphs 31
1-7 Eulerian Graphs 40
1-8 Hamiltonian Graphs 45
References and Further Reading 52
Exercises 53
2 ALGORITHMIC TECHNIQUES 55
2-1
Divide and Conquer and Partitioning 55
2-2
Dynamic Programming
56
2-3
Tree Based Algorithms
61
2-4
Backtracking 63
2-5
Recursion 66
2-6
Greedy Algorithms 69
2-7
Approximation 73
2-8
Geometric Methods 75
2-9
Problem Transformation
80
2-10 Integer Programming 83
2- 11 Probabilistic Techniques 85
References and Further Reading 87
Exercises 88
3 SHORTEST PATHS 90
3- 1 Dijkstra’s Algorithm: Vertex to Vertex 90
3-2 Floyd’s Algorithm: Vertex to All Vertices 97
3-3 Ford’s Algorithm: All Vertices to All
Vertices 103
3-4 Euclidean Shortest Paths: Sedgewick-Vitter
Heuristic 107
3- 5 Fibonacci Heaps and Dijkstra’s Algorithm 109
References and Further Reading 113
Exercises 113
4 TREES AND ACYCLIC DIGRAPHS 115
4- 1 Basic Concepts 115
4-2 Trees as Models 117
4-2-1 Search Tree Performance, 117
4-2-2 Abstract Models of
Computation, 119
4-2-3 Merge Trees, 120
4-2-4 Precedence Trees for Multiprocessor
Scheduling, 123
4-3 Minimum Spanning Trees 124
4-4 Geometric Minimum Spanning Trees 134
4-5 Acyclic Digraphs 135
4-5-1 Bill of Materials (Topological Sorting),
136
4-5-2 Deadlock Avoidance (Cycle Testing),
138
4-5-3 PERT (Longest Paths), 140
4- 5-4 Optimal Register Allocation (Tree
Labeling), 141
4- 6 Fibonacci Heaps and Mimimum Spanning
Trees 145
References and Further Reading 147
Exercises 148
5 DEPTH-FIRST SEARCH 750
5- 1 Introduction 150
5-2 Depth-First Search Algorithms 151
5- 2-1 Vertex Numbering, 151
5-2-2 Edge Classification: Undirected
Graphs, 156
IV
Contents
5-2-3 Edge Classification: Directed Graphs,
159
5-3 Orientation Algorithm 163
5-4 Strong Components Algorithm 167
5- 5 Block Algorithm 173
References and Further Reading 176
Exercises 176
6 CONNECTIVITY AND ROUTING
6- 1 Connectivity: Basic Concepts 178
6-2 Connectivity Models: Vulnerability and Reliable
Transmission 181
6-3 Network Flows: Basic Concepts 183
6-4 Maximum Flow Algorithm: Ford and
Fulkerson 190
6-5 Maximum Flow Algorithm: Dinic 197
6-6 Flow Models: Multiprocessor Scheduling 210
6-7 Connectivity Algorithms 212
6-8 Partial Permutation Routing on a
Hypercube 218
References and Further Reading 220
Exercises 221
7 GRAPH COLORING
7-1 Basic Concepts 223
7-2 Models: Constrained Scheduling and
Zero-Knowledge Passwords 225
7-3 Backtrack Algorithm 227
7-4 Five-Color Algorithm 231
References and Further Reading 235
Exercises 235
8
COVERS, DOMINATION, INDEPENDENT SETS,
MATCHINGS, AND FACTORS
8-1 Basic Concepts 237
8-2 Models 240
8-2-1 Independence Number and Parallel
Maximum, 240
8-2-2 Matching and Processor Scheduling,
242
8-2-3 Degree Constrained Matching and
Deadlock Freedom, 244
8-3 Maximum Matching Algorithm of
Edmonds 248
References and Further Reading 254
Exercises 254
9 PARALLEL ALGORITHMS 256
9-1 Systolic Array for Transitive Closure 256
9-2 Shared Memory Algorithms 262
9-2-1 Parallel Dijkstra Shortest Path
Algorithm (EREW), 262
9-2-2 Parallel Floyd Shortest Path
Algorithm {CREW), 264
9-2-3 Parallel Connected Components
Algorithm (CRCW), 265
9-2-4 Parallel Maximum Matching Using
Isolation {CREW), 270
9-3 Software Pipeline for Heaps 274
9-4 Tree Processor Connected Components
Algorithm 279
9-5 Hypercube Matrix Multiplication and Shortest
Paths 283
References and Further Reading 290
Exercises 291
10 COMPUTATIONAL COMPLEXITY 294
10-1 Polynomial and Pseudopolynomial
Problems 294
10-2 Nondeterministic Polynomial Algorithms 297
10-3 NP-Complete Problems 302
10-4 Random and Parallel Algorithms 309
References and Further Reading 313
Exercises 313
BIBLIOGRAPHY
315
INDEX
321