A Java Library of Graph Algorithms and Optimization

Introduction 1(2) Random Graph Generation 3(34) Random Permutation of n Objects 3(1) Random Graph 4(3) Random Bipartite Graph 7(3) Random Regular Graph 10(4) Random Spanning Tree 14(2) Random Labeled Tree 16(2) Random Unlabeled Rooted Tree 18(3) Random Connected Graph 21(3) Random Hamilton Graph 24(3) Random Maximum Flow Network 27(4) Random Isomorphic Graphs 31(3) Random Isomorphic Regular Graphs 34(3) Connectivity 37(52) Maximum Connectivity 37(2) Depth-First Search 39(4) Breadth-First Search 43(4) Connected Graph Testing 47(3) Connected Components 50(5) Cut Nodes 55(6) Strongly Connected Components 61(4) Minimal Equivalent Graph 65(8) Edge Connectivity 73(2) Minimum Spanning Tree 75(6) All Cliques 81(8) Paths and Cycles 89(90) Fundamental Set of Cycles 89(4) Shortest Cycle Length 93(3) One-Pair Shortest Path 96(6) All Shortest Path Length 102(3) Shortest Path Tree 105(4) All Pairs Shortest Paths 109(3) k Shortest Paths 112(11) k Shortest Paths without Repeated Nodes 123(19) Euler Circuit 142(4) Hamilton Cycle 146(5) Chinese Postman Tour 151(22) Traveling Salesman Problem 173(6) Planarity Testing 179(16) Graph Isomorphism Testing 195(12) Coloring 207(14) Node Coloring 207(5) Chromatic Polynomial 212(9) Graph Matching 221(22) Maximum Cardinality Matching 221(4) Minimum Sum Perfect Matching 225(18) Network Flow 243(30) Maximum Network Flow 243(11) Minimum Cost Network Flow 254(19) Packing and Covering 273(56) Assignment Problem 273(7) Bottleneck Assignment Problem 280(4) Quadratic Assignment Problem 284(20) Multiple Knapsack Problem 304(19) Set Covering Problem 323(2) Set Partitioning Problem 325(4) Linear Programming 329(12) Revised Simplex Method 329(5) Dual Simplex Method 334(7) Integer Programming 341(30) Zero-One Integer Programming 341(6) All Integer Programming 347(4) Mixed Integer Programming 351(20) Quadratic Programming 371(6) Appendix A: References 377(6) Appendix B: Graph-Theoretic Terms 383(2) Index of Procedures 385