Evans J.R., Minieka E. Optimization Algorithms for Networks and Graphs

Издательство Marcel Dekker, 1992, -499 pp.
The 1970s ushered in an exciting era of research and applications of networks and graphs in operations research, industrial engineering, and related disciplines. Network optimization has been an important area of research and application in its own right and, in addition, is increasingly important as a component of broader and more powerful decision support systems.
This is a text about optimization algorithms for problems that can be formulated on graphs and networks. The first edition of this text was unique in providing a comprehensive, cohesive, and clear treatment of this body of knowledge. Many new results and applications have appeared in the literature since that time. This edition provides many new applications and algorithms while maintaining the classic foundations on which contemporary algorithms have been developed.
The major changes in this edition are described below.
- The original chapters have been expanded and updated and include new material that originated over the past decade and a half. The latter includes such topics as partitioning algorithms for shortest paths, preflow-push algorithms for maximum flow, extensions of the postman problem, the network simplex method, and heuristic procedures for the traveling salesman problem. In addition, the introductory section of each chapter now includes many new and realistic application examples. - A new chapter on computer representation, algorithms, heuristics, and computational complexity has been added. The chapter on flow algorithms has been divided into two separate chapters: one on minimum-cost flow algorithms, and one dealing exclusively with maximum-flow algorithms..
- A computer software package, NETSOLVE, developed by James Jarvis and Douglas Shier, has been integrated with the text to provide students with the ability to solve larger applications than one can expect to by hand.
Introduction to Graphs and Networks.
Computer Representation and Solution.
Tree Algorithms.
Shortest-Path Algorithms.
Minimum-Cost Flow Algorithms.
Maximum-Flow Algorithms.
Matching and Assignment Algorithms.
The Postman and Related Arc Routing Problems.
The Traveling Salesman and Related Vertex Routing Problems.
Location Problems.
Project Networks.
User's Guide to NETSOLVE.