Graphs, Algorithms, and OptimizationGraph 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. |
Contents
1 Graphs and Their Complements | 1 |
2 Paths and Walks | 23 |
3 Some Special Classes of Graphs | 47 |
4 Trees and Cycles | 63 |
5 The Structure of Trees | 89 |
6 Connectivity | 119 |
7 Alternating Paths and Matchings | 139 |
8 Network Flows | 161 |
11 Graph Colorings | 245 |
12 Planar Graphs | 275 |
13 Graphs and Surfaces | 327 |
14 Linear Programming | 387 |
15 The PrimalDual Algorithm | 417 |
16 Discrete Linear Programming | 449 |
Bibliography | 469 |
| 477 | |
Other editions - View all
Common terms and phrases
2-connected adjacency list algorithm alternating paths assign augmenting path B₁ bipartite graph branches breadth-first color column complete graph compute connected graph construct corresponding cut-vertex DEG(u DEG(v deleted denote depth-first depth-first search diagonal digraph disc dual edge uv edge-cut edges of G endpoints Euler tour face facial cycle feasible solution follows G contains graph G graph theory hamilton cycle illustrated in Figure integer integer linear program isomorphic iteration LB-tree leading chord LEMMA Let G linear program linked list LowPt[v matrix maximum minimum node NP-complete number of edges number of steps number of vertices P₁ perfect matching planar embedding planar graph polygons Prim's algorithm primal problem projective plane PROOF QSize recursive rooted trees rotation system ScanQ Show shown in Figure spanning tree st-paths strong component subgraph subtree Suppose surface theorem topological torus triangulation u₁ v₁ variables vertex cover