William Kocay, Donald L. Kreher

eBook, PDF

Graphs, Algorithms, and Optimization (eBook, PDF)

Beschreibung

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.

Technische Details

• Geräte: PC
• mit Kopierschutz
• Größe: 17.95MB

Autor

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.

Produktdetails

• Verlag: Taylor & Francis eBooks
• Seitenzahl: 504
• Erscheinungstermin: 20. September 2017
• Englisch
• ISBN-13: 9781351989121
• Artikelnr.: 54156419

Rezensionen

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