Preface; 1 Graphs and Their Complements; 2 Paths and Walks; 3 Subgraphs; 4 Some Special Classes of Graphs; 5 Trees and Cycles; 6 The Structure of Trees; 7 Connectivity; 8 Graphs and Symmetry; 9 Alternating Paths and Matchings; 10 Network Flows; 11 Hamilton Cycles; 12 Digraphs; 13 Graph Colorings; 14 Planar Graphs; 15 Graphs and Surfaces; 16 The Klein Bottle and the Double Torus; 17 Linear Programming; 18 The Primal-Dual Algorithm; 19 Discrete Linear Programming; Bibliography; Index
William Kocay is a professor in the Department
of Computer Science at St. Paul's College of the University of
Manitoba, Canada.
Donald Kreher is a professor of mathematical
sciences at Michigan Technological University, Houghton,
Michigan.
Given this is the second edition of a respected text, it is
important to examine what has changed and how the text has
improved. Using an “algorithmic viewpoint,” the authors explore the
standard aspects of graph theory—complements, paths, walks,
subgraphs, trees, cycles, connectivity, symmetry, network flows,
digraphs, colorings, graph matchings, and planar graphs. The
expanded topics include explorations of subgraph counting, graphs
and symmetries via permutation groups, graph embeddings on
topological surfaces such as the Klein bottle and the double torus,
and the connections of graphs to linear programming, including the
primal-dual algorithm and discrete considerations, where the
integral variables are bounded. Other text changes include some
proof corrections and meaningful content revisions. Each chapter
section contains rich exercise sets, complemented by chapter notes
and an extensive bibliography. The authors’ claim is correct—their
style is "rigorous, but informal," insightful, and it works. The
text’s algorithms are generic in style, and usable with any major
language. In summary, aimed at computer science and mathematics
students, this revised text on graph theory will both challenge
upper-level undergraduates and provide a comprehensive foundation
for graduate students.
--J. Johnson, Western Washington University
|
Ask a Question About this Product More... |
|
