Graphs, Algorithms, and Optimization

Description

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.