Graphs, Algorithms, and Optimization
Purchasing Options
Features
Summary
Graph theory offers a rich source of problems and techniques for programming and data structure development, as well as for understanding computing theory, including NP-Completeness and polynomial reduction.
A comprehensive text, Graphs, Algorithms, and Optimization features clear exposition on modern algorithmic graph theory presented in a rigorous yet approachable way. The book covers major areas of graph theory including discrete optimization and its connection to graph algorithms. The authors explore surface topology from an intuitive point of view and include detailed discussions on linear programming that emphasize graph theory problems useful in mathematics and computer science. Many algorithms are provided along with the data structure needed to program the algorithms efficiently. The book also provides coverage on algorithm complexity and efficiency, NP-completeness, linear optimization, and linear programming and its relationship to graph algorithms.
Written in an accessible and informal style, this work covers nearly all areas of graph theory. Graphs, Algorithms, and Optimization provides a modern discussion of graph theory applicable to mathematics, computer science, and crossover applications.
Table of Contents
GRAPHS AND THEIR COMPLEMENTS
Degree sequences
Analysis
PATHS AND WALKS
Complexity
Walks
The shortest path problem
Weighted graphs and Dijkstra's algorithm
Data structures. Floyd's algorithm
SOME SPECIAL CLASSES OF GRAPHS
Bipartite graphs
Line graphs
Moore graphs
Euler tours
TREES AND CYCLES
Fundamental
Co-trees and bonds
Spanning tree algorithms
THE STRUCTURE OF TREES
Non-rooted
Read's tree encoding algorithm
Generating rooted trees
Generating non-rooted trees
Prüfer sequences
Spanning trees
The matrix-tree theorem
CONNECTIVITY
Blocks
Finding the blocks of a graph
The depth-first search
ALTERNATING PATHS AND MATCHINGS.
The Hungarian algorithm
Perfect matchings and 1-factorizations
The subgraph problem
Coverings in bipartite graphs
Tutte's theorem
NETWORK FLOWS
Introduction
The Ford-Fulkerson algorithm
Matchings and flows
Menger's theorems
Disjoint paths and separating sets
Notes
HAMILTON CYCLES
The crossover algorithm
The Hamilton closure
The extended multi-path algorithm
The traveling salesman problem
The ?TSP
Christofides' algorithm
DIGRAPHS
Activity graphs, Critical paths
Topological order
Strong components
An application to fabrics
Tournaments
Satisfiability
GRAPH COLORINGS
Cliques
Mycielski's construction
Critical graphs
Chromatic polynomials
Edge colorings
NP-completeness
PLANAR GRAPHS
Jordan curves
Graph minors
Subdivisions
Euler's formula
Rotation systems
Dual graphs
Platonic solids
Triangulations
The sphere 5
Whitney's theorem
Medial digraphs
The 4-color problem
Straight line drawings
Kuratowski's theorem
The Hopcroft-Tarjan Algorithm
GRAPHS AND SURFACES
Surfaces
Graph embeddings
Graphs on the torus
Graphs on the projective plane
LINEAR PROGRAMMING
The simplex algorithm
Cycling
THE PRIMAL-DUAL ALGORITHM
Alternate form of the primal and its dual
Geometric interpretation
Complementary slackness
The dual of the shortest path problem
The primal-dual algorithm
DISCRETE LINEAR PROGRAMMING
Backtracking
Branch and bound
Unimodular matrices
BIBLIOGRAPHY
INDEX
Editorial Reviews
"The book is written in an easygoing style, and the proofs are concisely presented and easy to follow. … [This book] would serve as a fine textbook for an undergraduate graph theory course for math majors. … [I]t is well-written, the proofs are easy to follow, the figures complement the text, and the exercises are helpful to student understanding …"
- MAA Online
"A valuable resource for mathematics and computer science students and professionals…contains a wealth of information on algorithms and the data structures needed to program them efficiently…the graph theory presented is rigorous, but the style is informal."
- L'Enseignement Mathématique
