Because of its portability and platform-independence, Java is the ideal computer programming language to use when working on graph algorithms and other mathematical programming problems. Collecting some of the most popular graph algorithms and optimization procedures, A Java Library of Graph Algorithms and Optimization provides the source code for a library of Java programs that can be used to solve problems in graph theory and combinatorial optimization. Self-contained and largely independent, each topic starts with a problem description and an outline of the solution procedure, followed by its parameter list specification, source code, and a test example that illustrates the usage of the code.
The book begins with a chapter on random graph generation that examines bipartite, regular, connected, Hamilton, and isomorphic graphs as well as spanning, labeled, and unlabeled rooted trees. It then discusses connectivity procedures, followed by a paths and cycles chapter that contains the Chinese postman and traveling salesman problems, Euler and Hamilton cycles, and shortest paths. The author proceeds to describe two test procedures involving planarity and graph isomorphism. Subsequent chapters deal with graph coloring, graph matching, network flow, and packing and covering, including the assignment, bottleneck assignment, quadratic assignment, multiple knapsack, set covering, and set partitioning problems. The final chapters explore linear, integer, and quadratic programming. The appendices provide references that offer further details of the algorithms and include the definitions of many graph theory terms used in the book.
Author(s): Hang T. Lau
Series: Discrete Mathematics and Its Applications
Edition: 1st
Publisher: Chapman and Hall/CRC
Year: 2006
Language: English
Pages: 386
Tags: Algorithms Data Structures Genetic Memory Management Programming Computers Technology Reference Almanacs Yearbooks Atlases Maps Careers Catalogs Directories Consumer Guides Dictionaries Thesauruses Encyclopedias Subject English as a Second Language Etiquette Foreign Study Genealogy Quotations Survival Emergency Preparedness Test Preparation Words Grammar Writing Research Publishing Number Systems Mathematics Science Math Computer New Used Rental Textbooks Specialty Boutique Algebra Trigonometry
A Java Library of Graph Algorithms and Optimization......Page 4
The Author......Page 7
Contents......Page 8
Untitled......Page 11
C7184ch1......Page 12
Procedure parameters......Page 13
Example......Page 15
Procedure parameters......Page 16
Example......Page 18
Procedure parameters......Page 19
Output......Page 22
Procedure parameters......Page 23
Example......Page 24
Procedure parameters......Page 25
Example......Page 26
Procedure parameters......Page 27
Example......Page 29
Procedure parameters......Page 30
Example......Page 32
Procedure parameters......Page 33
Example......Page 35
1.10 Random Maximum Flow Network......Page 36
Procedure parameters......Page 37
Example......Page 39
Procedure parameters......Page 40
Example......Page 41
Output......Page 42
Procedure parameters......Page 43
Example......Page 44
Output......Page 45
Appendix A: References......Page 0
Procedure parameters......Page 46
2.2 Depth-First Search......Page 48
Procedure parameters......Page 49
Example......Page 51
2.3 Breadth-First Search......Page 52
Procedure parameters......Page 53
Example......Page 55
Procedure parameters......Page 56
Output......Page 58
Procedure parameters......Page 59
Output......Page 63
Procedure parameters......Page 64
Output......Page 69
Procedure parameters......Page 70
Example......Page 73
Procedure parameters......Page 74
Output......Page 81
Procedure parameters......Page 82
Example......Page 83
2.10 Minimum Spanning Tree......Page 84
Procedure parameters (Prim’s method)......Page 85
Output......Page 86
Procedure parameters (Kruskal’s method)......Page 87
Example......Page 89
2.11 All Cliques......Page 90
Procedure parameters......Page 91
Output......Page 96
Procedure parameters......Page 97
Example......Page 100
Procedure parameters......Page 101
Output......Page 103
Procedure parameters......Page 104
Output......Page 109
Procedure parameters......Page 110
Example......Page 112
3.5 Shortest Path Tree......Page 113
Procedure parameters......Page 114
Example......Page 116
Procedure parameters......Page 117
Example......Page 119
3.7 k Shortest Paths......Page 120
Procedure parameters......Page 121
Example......Page 130
3.8 k Shortest Paths without Repeated Nodes......Page 131
Procedure parameters......Page 132
Example......Page 149
3.9 Euler Circuit......Page 150
Procedure parameters......Page 151
Example......Page 153
3.10 Hamilton Cycle......Page 154
Procedure parameters......Page 155
Example......Page 158
3.11 Chinese Postman Tour......Page 159
Procedure parameters......Page 160
Example......Page 180
Procedure parameters......Page 181
Output......Page 185
Procedure parameters......Page 186
Output......Page 200
Procedure parameters......Page 201
Example......Page 210
Output......Page 211
Procedure parameters......Page 212
Example......Page 216
6.2 Chromatic Polynomial......Page 217
Procedure parameters......Page 218
Example......Page 223
Output......Page 224
Procedure parameters......Page 225
Output......Page 228
Procedure parameters......Page 229
Example......Page 244
Output......Page 245
Procedure parameters......Page 246
Example......Page 255
Output......Page 256
Procedure parameters......Page 257
Example......Page 274
Output......Page 275
Procedure parameters......Page 276
Output......Page 282
Procedure parameters......Page 283
Example......Page 286
Procedure parameters......Page 287
Example......Page 306
9.4 Multiple Knapsack Problem......Page 307
Procedure parameters......Page 308
Example......Page 325
Procedure parameters......Page 326
Example......Page 327
9.6 Set Partitioning Problem......Page 328
Procedure parameters......Page 329
Output......Page 331
10.1 Revised Simplex Method......Page 332
Procedure parameters......Page 333
Example......Page 336
10.2 Dual Simplex Method......Page 337
Procedure parameters......Page 339
Example......Page 342
Output......Page 343
Procedure parameters......Page 344
Example......Page 349
11.2 All Integer Programming......Page 350
Procedure parameters......Page 351
Example......Page 353
11.3 Mixed Integer Programming......Page 354
Procedure parameters......Page 355
Example......Page 372
Output......Page 373
Procedure parameters......Page 374
Output......Page 379
Appendix A: References......Page 380
Appendix B: Graph-Theoretic Terms......Page 385
