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