Preface |
|
xi | |
Editors |
|
xiii | |
Contributors |
|
xv | |
|
Section I Basic Concepts and Algorithms |
|
|
|
Chapter 1 Basic Concepts in Graph Theory and Algorithms |
|
|
3 | (18) |
|
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 2 Basic Graph Algorithms |
|
|
21 | (38) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 3 Depth-First Search and Applications |
|
|
59 | (20) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Section II Flows in Networks |
|
|
|
Chapter 4 Maximum Flow Problem |
|
|
79 | (34) |
|
|
|
|
|
Chapter 5 Minimum Cost Flow Problem |
|
|
113 | (44) |
|
Balachandran Vaidyanathan |
|
|
|
|
|
Chapter 6 Multicommodity Flows |
|
|
157 | (20) |
|
Balachandran Vaidyanathan |
|
|
|
|
|
Section III Algebraic Graph Theory |
|
|
|
Chapter 7 Graphs and Vector Spaces |
|
|
177 | (14) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
|
Chapter 8 Incidence, Cut, and Circuit Matrices of a Graph |
|
|
191 | (24) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
|
Chapter 9 Adjacency Matrix and Signal Flow Graphs |
|
|
215 | (12) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
|
Chapter 10 Adjacency Spectrum and the Laplacian Spectrum of a Graph |
|
|
227 | (20) |
|
|
Chapter 11 Resistance Networks, Random Walks, and Network Theorems |
|
|
247 | (26) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
|
Section IV Structural Graph Theory |
|
|
|
|
273 | (18) |
|
|
|
Chapter 13 Connectivity Algorithms |
|
|
291 | (24) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 14 Graph Connectivity Augmentation |
|
|
315 | (34) |
|
|
|
|
349 | (24) |
|
|
Chapter 16 Matching Algorithms |
|
|
373 | (30) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 17 Stable Marriage Problem |
|
|
403 | (16) |
|
|
Chapter 18 Domination in Graphs |
|
|
419 | (30) |
|
|
|
Chapter 19 Graph Colorings |
|
|
449 | (26) |
|
|
|
|
|
Chapter 20 Planarity and Duality |
|
|
475 | (14) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
|
Chapter 21 Edge Addition Planarity Testing Algorithm |
|
|
489 | (36) |
|
|
Chapter 22 Planarity Testing Based on PC-Trees |
|
|
525 | (12) |
|
|
|
537 | (50) |
|
|
|
Section VI Interconnection Networks |
|
|
|
Chapter 24 Introduction to Interconnection Networks |
|
|
587 | (40) |
|
|
|
|
|
627 | (26) |
|
|
|
|
Chapter 26 Graph Embedding and Interconnection Networks |
|
|
653 | (38) |
|
|
|
|
Section VII Special Graphs |
|
|
|
Chapter 27 Program Graphs |
|
|
691 | (16) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 28 Perfect Graphs |
|
|
707 | (44) |
|
|
|
Chapter 29 Tree-Structured Graphs |
|
|
751 | (78) |
|
|
|
Section VIII Partitioning |
|
|
|
Chapter 30 Graph and Hypergraph Partitioning |
|
|
829 | (50) |
|
|
|
|
|
|
879 | (44) |
|
|
|
Chapter 32 Hybrid Analysis and Combinatorial Optimization |
|
|
923 | (22) |
|
|
Section X Probabilistic Methods, Random Graph Models, and Randomized Algorithms |
|
|
|
Chapter 33 Probabilistic Arguments in Combinatorics |
|
|
945 | (52) |
|
|
Chapter 34 Random Models and Analyses for Chemical Graphs |
|
|
997 | (14) |
|
|
|
|
Chapter 35 Randomized Graph Algorithms: Techniques and Analysis |
|
|
1011 | (16) |
|
|
|
Section XI Coping with NP-Completeness |
|
|
|
Chapter 36 General Techniques for Combinatorial Approximation |
|
|
1027 | (8) |
|
|
Chapter 37 ε-Approximation Schemes for the Constrained Shortest Path Problem |
|
|
1035 | (6) |
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 38 Constrained Shortest Path Problem: Lagrangian Relaxation-Based Algorithmic Approaches |
|
|
1041 | (22) |
|
|
Krishnaiyan "KT" Thulasiraman |
|
|
Chapter 39 Algorithms for Finding Disjoint Paths with QoS Constraints |
|
|
1063 | (12) |
|
|
|
Chapter 40 Set-Cover Approximation |
|
|
1075 | (4) |
|
|
Chapter 41 Approximation Schemes for Fractional Multicommodity Flow Problems |
|
|
1079 | (18) |
|
|
Chapter 42 Approximation Algorithms for Connectivity Problems |
|
|
1097 | (18) |
|
|
Chapter 43 Rectilinear Steiner Minimum Trees |
|
|
1115 | (26) |
|
|
|
Chapter 44 Fixed-Parameter Algorithms and Complexity |
|
|
1141 | (56) |
|
|
Index |
|
1197 | |