Lau A Java Library of Graph Algorithms and Optimization

1. Auflage 2010
ISBN: 978-1-58488-719-5
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 386 Seiten

Reihe: Discrete Mathematics and Its Applications

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.

Zielgruppe

Researchers, applied mathematicians, computer scientists, and engineers.

Autoren/Hrsg.

Lau, Hang T.

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmier- und Skriptsprachen

Inhaltsverzeichnis

INTRODUCTION

RANDOM GRAPH GENERATION
Random Permutation of n Objects
Random Graph
Random Bipartite Graph
Random Regular Graph
Random Spanning Tree
Random Labeled Tree
Random Unlabeled Rooted Tree
Random Connected Graph
Random Hamilton Graph
Random Maximum Flow Network
Random Isomorphic Graphs
Random Isomorphic Regular Graphs

CONNECTIVITY
Maximum Connectivity
Depth-First Search
Breadth-First Search
Connected Graph Testing
Connected Components
Cut Nodes
Strongly Connected Components
Minimal Equivalent Graph
Edge Connectivity
Minimum Spanning Tree
All Cliques

PATHS AND CYCLES
Fundamental Set of Cycles
Shortest Cycle Length
One-Pair Shortest Path
All Shortest Path Length
Shortest Path Tree
All Pairs Shortest Paths
k Shortest Paths
k Shortest Paths without Repeated Nodes
Euler Circuit
Hamilton Cycle
Chinese Postman Tour
Traveling Salesman Problem

PLANARITY TESTING

GRAPH ISOMORPHISM TESTING

COLORING
Node Coloring
Chromatic Polynomial

GRAPH MATCHING
Maximum Cardinality Matching
Minimum Sum Perfect Matching

NETWORK FLOW
Maximum Network Flow
Minimum Cost Network Flow

PACKING AND COVERING
Assignment Problem
Bottleneck Assignment Problem
Quadratic Assignment Problem
Multiple Knapsack Problem
Set Covering Problem
Set Partitioning Problem

LINEAR PROGRAMMING
Revised Simplex Method
Dual Simplex Method

INTEGER PROGRAMMING
Zero-One Integer Programming
All Integer Programming
Mixed Integer Programming

QUADRATIC PROGRAMMING

APPENDIX A: REFERENCES
APPENDIX B: GRAPH-THEORETIC TERMS
INDEX OF PROCEDURES