Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

The fusion between graph theory and combinatorial optimization has led to theoretically profound and practically useful algorithms, yet there is no book that currently covers both areas together. Handbook of Graph Theory, Combinatorial Optimization, and Algorithms is the first to present a unified, comprehensive treatment of both graph theory and combinatorial optimization.

Divided into 11 cohesive sections, the handbook’s 44 chapters focus on graph theory, combinatorial optimization, and algorithmic issues. The book provides readers with the algorithmic and theoretical foundations to:

• Understand phenomena as shaped by their graph structures
• Develop needed algorithmic and optimization tools for the study of graph structures
• Design and plan graph structures that lead to certain desirable behavior

With contributions from more than 40 worldwide experts, this handbook equips readers with the necessary techniques and tools to solve problems in a variety of applications. Readers gain exposure to the theoretical and algorithmic foundations of a wide range of topics in graph theory and combinatorial optimization, enabling them to identify (and hence solve) problems encountered in diverse disciplines, such as electrical, communication, computer, social, transportation, biological, and other networks.

Table of Contents

SECTION I – Basic Concepts and Algorithms
CHAPTER 1 – Basic Concepts in Graph Theory and Algorithms
CHAPTER 2 – Basic Graph Algorithms
CHAPTER 3 – Depth-First Search and Applications

SECTION II – Flows in Networks
CHAPTER 4 – Maximum Flow Problem
CHAPTER 5 – Minimum Cost Flow Problem
CHAPTER 6 – Multicommodity Flows

SECTION III – Algebraic Graph Theory
CHAPTER 7 – Graphs and Vector Spaces
CHAPTER 8 – Incidence, Cut, and Circuit Matrices of a Graph
CHAPTER 9 – Adjacency Matrix and Signal Flow Graphs
CHAPTER 10 – Adjacency Spectrum and the Laplacian Spectrum of a Graph
CHAPTER 11 – Resistance Networks, Random Walks, and Network Theorems

SECTION IV – Structural Graph Theory
CHAPTER 12 – Connectivity
CHAPTER 13 – Connectivity Algorithms
CHAPTER 14 – Graph Connectivity Augmentation
CHAPTER 15 – Matchings
CHAPTER 16 – Matching Algorithms
CHAPTER 17 – Stable Marriage Problem
CHAPTER 18 – Domination in Graphs
CHAPTER 19 – Graph Colorings

SECTION V – Planar Graphs
CHAPTER 20 – Planarity and Duality
CHAPTER 21 – Edge Addition Planarity Testing Algorithm
CHAPTER 22 – Planarity Testing Based on PC-Trees
CHAPTER 23 – Graph Drawing
SECTION VI – Interconnection Networks
CHAPTER 24 – Introduction to Interconnection Networks
CHAPTER 25 – Cayley Graphs
CHAPTER 26 – Graph Embedding and Interconnection Networks

SECTION VII – Special Graphs
CHAPTER 27 – Program Graphs
CHAPTER 28 – Perfect Graphs
CHAPTER 29 – Tree-Structured Graphs

SECTION VIII – Partitioning
CHAPTER 30 – Graph and Hypergraph Partitioning

SECTION IX – Matroids
CHAPTER 31 – Matroids
CHAPTER 32 – Hybrid Analysis and Combinatorial Optimization

SECTION X – Probabilistic Methods, Random Graph Models, and Randomized Algorithms
CHAPTER 33 – Probabilistic Arguments in Combinatorics
CHAPTER 34 – Random Models and Analyses for Chemical Graphs
CHAPTER 35 – Randomized Graph Algorithms: Techniques and Analysis

SECTION XI – Coping with NP-Completeness
CHAPTER 36 – General Techniques for Combinatorial Approximation
CHAPTER 37 – ε-Approximation Schemes for the Constrained Shortest Path Problem
CHAPTER 38 – Constrained Shortest Path Problem: Lagrangian Relaxation-Based Algorithmic Approaches
CHAPTER 39 – Algorithms for Finding Disjoint Paths with QoS Constraints
CHAPTER 40 – Set-Cover Approximation
CHAPTER 41 – Approximation Schemes for Fractional Multicommodity Flow Problems
CHAPTER 42 – Approximation Algorithms for Connectivity Problems
CHAPTER 43 – Rectilinear Steiner Minimum Trees
CHAPTER 44 – Parameter Algorithms and Complexity