Graphs, Algorithms, and Optimization

Description

CRC Press, 2005. — 305 p.Our objective in writing this book is to present the theory of graphs from an algorithmic viewpoint. We present the graph theory in a rigorous, but informal style and cover most of the main areas of graph theory. The ideas of surface topology are presented from an intuitive point of view. We have also included a discussion on linear programming that emphasizes problems in graph theory. The text is suitable for students in computer science or mathematics programs. Graph theory is a rich source of problems and techniques for programming and data structure development, as well as for the theory of computing, including NP-completeness and polynomial reduction. This book could be used a textbook for a third or fourth year course on graph algorithms which contains a programming content, or for a more advanced course at the fourth year or graduate level. It could be used in a course in which the programming language is any major programming language (e.g., C, C++, Java). The algorithms are presented in a generic style and are not dependent on any particular programming language. The text could also be used for a sequence of courses like Graph Algorithms I and Graph Algorithms II. The courses offered would depend on the selection of chapters included. A typical course will begin with Chapters 1, 2, 3, and 4 . At this point, a number of options are available. A possible first course would consist of Chapters 1, 2, 3, 4, 6, 8, 9, 10, 11, and 12, and a first course stressing optimization would consist of Chapters 1, 2, 3, 4, 8, 9, 10, 14, 15, and 16 . Experience indicates that the students consider these substantial courses. One or two chapters could be omitted for a lighter course.Graphs and Their Complements Paths and Walks Some Special Classes of Graphs Trees and Cycles The Structure of Trees Connectivity Alternating Paths and Matchings Network Flows Hamilton Cycles Digraphs Graph Colorings Planar Graphs Graphs and Surfaces Linear Programming The Primal-Dual Algorithm Discrete Linear Programming