Graphs, Algorithms, and Optimization

Content: Cover
 Half Title
 Title Page
 Copyright Page
 Dedication
 Contents
 Preface
 1 Graphs and Their Complements
 1.1 Introduction
 Exercises
 1.2 Degree sequences
 Exercises
 1.3 Analysis
 Exercises
 1.4 Notes
 2 Paths and Walks
 2.1 Introduction
 2.2 Complexity
 Exercises
 2.3 Walks
 Exercises
 2.4 The shortest-path problem
 2.5 Weighted graphs and Dijkstra's algorithm
 Exercises
 2.6 Data structures
 2.7 Floyd's algorithm
 Exercises
 2.8 Notes
 3 Some Special Classes of Graphs
 3.1 Bipartite graphs
 Exercises
 3.2 Line graphs
 Exercises
 3.3 Moore graphs
 Exercises
 3.4 Euler tours. 3.4.1 An Euler tour algorithmExercises
 3.5 Notes
 4 Trees and Cycles
 4.1 Introduction 63 Exercises
 4.2 Fundamental cycles
 Exercises
 4.3 Co-trees and bonds
 Exercises
 4.4 Spanning tree algorithms
 4.4.1 Prim's algorithm
 Data structures
 Exercises
 4.4.2 Kruskal's algorithm
 Data structures and complexity
 4.4.3 The Cheriton-Tarjan algorithm
 Exercises
 4.4.4 Leftist binary trees
 Exercises
 4.5 Notes
 5 The Structure of Trees
 5.1 Introduction
 5.2 Non-rooted trees
 Exercises
 5.3 Read's tree encoding algorithm
 5.3.1 The decoding algorithm
 Exercises
 5.4 Generating rooted trees. Exercises5.5 Generating non-rooted trees
 Exercises
 5.6 Priifer sequences
 5.7 Spanning trees
 5.8 The matrix-tree theorem
 Exercises
 5.9 Notes
 6 Connectivity
 6.1 Introduction
 Exercises
 6.2 Blocks
 6.3 Finding the blocks of a graph
 Exercises
 6.4 The depth-first search
 6.4.1 Complexity
 Exercises
 6.5 Notes
 7 Alternating Paths and Matchings
 7.1 Introduction
 Exercises
 7.2 The Hungarian algorithm
 7.2.1 Complexity
 Exercises
 7.3 Perfect matchings and 1-factorizations
 Exercises
 7.4 The sub graph problem
 7.5 Coverings in bipartite graphs
 7.6 Tutte's theorem
 Exercises
 7.7 Notes. 8 Network Flows8.1 Introduction
 8.2 The Ford-Fulkerson algorithm
 Exercises
 8.3 Matchings and flows
 Exercises
 8.4 Menger's theorems
 Exercises
 8.5 Disjoint paths and separating sets
 Exercises
 8.6 Notes
 9 Hamilton Cycles
 9.1 Introduction
 Exercises
 9.2 The crossover algorithm
 9.2.1 Complexity
 Exercises
 9.3 The Hamilton closure
 Exercises
 9.4 The extended multi-path algorithm
 9.4.1 Data structures for the segments
 Exercises
 9.5 Decision problems, NP-completeness
 Exercises
 9.6 The traveling salesman problem
 Exercises
 9.7 The TSP
 9.8 Christofides' algorithm
 Exercises. 9.9 Notes10 Digraphs
 10.1 Introduction
 10.2 Activity graphs, critical paths
 10.3 Topological order
 Exercises
 10.4 Strong components
 Exercises
 10.4.1 An application to fabrics
 Exercises
 10.5 Tournaments
 Exercises
 10.6 2-Satisfiability
 Exercises
 10.7 Notes
 11 Graph Colorings
 11.1. Introduction
 11.1.1 Intersecting lines in the plane
 Exercises
 11.2 Cliques
 11.3 Mycielski's construction
 11.4 Critical graphs
 Exercises
 11.5 Chromatic polynomials
 Exercises
 11.6 Edge colorings
 11.6.1 Complexity
 Exercises
 11.7 NP-completeness
 11.8 Notes
 12 Planar Graphs
 12.1 Introduction.