Handbook.of.Graph.Theory.Combinatorial.Optimization.and.Algorithms.158

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