ABSTRACT

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 c

part |2 pages

SECTION I - Basic Concepts and Algorithms

chapter 2|38 pages

- Basic Graph Algorithms

chapter 3|18 pages

- Depth-First Search and Applications

part |2 pages

SECTION II - Flows in Networks

chapter 4|34 pages

- Maximum Flow Problem

chapter 5|44 pages

- Minimum Cost Flow Problem

chapter 6|18 pages

- Multicommodity Flows

part |2 pages

SECTION III - Algebraic Graph Theory

part |2 pages

SECTION IV - Structural Graph Theory

chapter 12|18 pages

- Connectivity

chapter 13|24 pages

- Connectivity Algorithms

chapter 14|34 pages

- Graph Connectivity Augmentation

chapter 15|24 pages

- Matchings

chapter 16|30 pages

- Matching Algorithms

chapter 17|16 pages

- Stable Marriage Problem

chapter 18|30 pages

- Domination in Graphs

chapter 19|24 pages

- Graph Colorings

part |2 pages

SECTION V - Planar Graphs

chapter 20|14 pages

- Planarity and Duality

chapter 21|36 pages

- Edge Addition Planarity Testing Algorithm

chapter 22|12 pages

- Planarity Testing Based on PC-Trees

chapter 23|48 pages

- Graph Drawing

part |2 pages

SECTION VI - Interconnection Networks

chapter 24|40 pages

- Introduction to Interconnection Networks

chapter 25|26 pages

- Cayley Graphs

part |2 pages

SECTION VII - Special Graphs

chapter 27|16 pages

- Program Graphs

chapter 28|44 pages

- Perfect Graphs

chapter 29|76 pages

- Tree-Structured Graphs

part |2 pages

SECTION VIII - Partitioning

chapter 30|48 pages

- Graph and Hypergraph Partitioning

part |2 pages

SECTION IX - Matroids

chapter 31|44 pages

- Matroids

part |2 pages

SECTION X - Probabilistic Methods, Random Graph Models, and Randomized Algorithms

part |2 pages

SECTION XI - Coping with NP-Completeness