Table of Contents
GRAPHS AND THEIR COMPLEMENTS Degree sequences Analysis
PATHS AND WALKS Complexity Walks The shortest path problem Weighted graphs and Dijkstra's algorithm Data structures. Floyd's algorithm
SOME SPECIAL CLASSES OF GRAPHS Bipartite graphs Line graphs Moore graphs Euler tours
TREES AND CYCLES Fundamental Co-trees and bonds Spanning tree algorithms THE STRUCTURE OF TREES Non-rooted Read's tree encoding algorithm Generating rooted trees Generating non-rooted trees Prüfer sequences Spanning trees The matrix-tree theorem
CONNECTIVITY Blocks Finding the blocks of a graph The depth-first search ALTERNATING PATHS AND MATCHINGS.
The Hungarian algorithm Perfect matchings and 1-factorizations The subgraph problem Coverings in bipartite graphs Tutte's theorem
NETWORK FLOWS Introduction The Ford-Fulkerson algorithm Matchings and flows Menger's theorems Disjoint paths and separating sets Notes
HAMILTON CYCLES The crossover algorithm The Hamilton closure The extended multi-path algorithm The traveling salesman problem The ?TSP Christofides' algorithm
DIGRAPHS Activity graphs, Critical paths Topological order Strong components An application to fabrics Tournaments Satisfiability
GRAPH COLORINGS Cliques Mycielski's construction Critical graphs Chromatic polynomials Edge colorings NP-completeness
PLANAR GRAPHS Jordan curves Graph minors Subdivisions Euler's formula Rotation systems Dual graphs Platonic solids Triangulations The sphere 5
Whitney's theorem Medial digraphs The 4-color problem Straight line drawings Kuratowski's theorem The Hopcroft-Tarjan Algorithm
GRAPHS AND SURFACES Surfaces Graph embeddings Graphs on the torus Graphs on the projective plane
LINEAR PROGRAMMING The simplex algorithm Cycling
THE PRIMAL-DUAL ALGORITHM Alternate form of the primal and its dual Geometric interpretation Complementary slackness The dual of the shortest path problem The primal-dual algorithm
DISCRETE LINEAR PROGRAMMING Backtracking Branch and bound Unimodular matrices
BIBLIOGRAPHY INDEX
