ALGORITHMIC GRAPH THEORY AND PERFECT GRAPHS SECOND EDITIONPDF电子书下载

CHAPTER 1 Graph Theoretic Foundations 1

1.Basic Definitions and Notations 1

2.Intersection Graphs 9

3.Interval Graphs—A Sneak Preview of the Notions Coming Up 13

4.Summary 17

Exercises 18

Bibliography 20

CHAPTER 2 The Design of Efficient Algorithms 22

1.The Complexity of Computer Algorithms 22

2.Data Structures 31

3.How to Explore a Graph 37

4.Transitive Tournaments and Topological Sorting 42

Exercises 45

Bibliography 48

CHAPTER 3 Perfect Graphs 51

1.The Star of the Show 51

2.The Perfect Graph Theorem 53

3.p-Critical and Partitionable Graphs 58

4.A Polyhedral Characterization of Perfect Graphs 62

5.A Polyhedral Characterization of p-Critical Graphs 65

6.The Strong Perfect Graph Conjecture 71

Exercises 75

Bibliography 77

CHAPTER 4 Triangulated Graphs 81

1.Introduction 81

2.Characterizing Triangulated Graphs 81

3.Recognizing Triangulated Graphs by Lexicographic Breadth-First Search 84

4.The Complexity of Recognizing Triangulated Graphs 87

5.Triangulated Graphs as Intersection Graphs 91

6.Triangulated Graphs Are Perfect 94

7.Fast Algorithms for the COLORING，CLIQUE， STABLE SET， and CLIQUE-COVER Problems on Triangulated Graphs 98

Exercises 100

Bibliography 102

CHAPTER 5 Comparability Graphs 105

1.Γ-Chains and Implication Classes 105

2.Uniquely Partially Orderable Graphs 109

3.The Number of Transitive Orientations 113

4.Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations 120

5.The 1*-Matroid of a Graph 124

6.The Complexity of Comparability Graph Recognition 129

7.Coloring and Other Problems on Comparability Graphs 132

8.The Dimension of Partial Orders 135

Exercises 139

Bibliography 142

CHAPTER 6 Split Graphs 149

1.An Introduction to Chapters 6-8： Interval，Permutation， and Split Graphs 149

2.Characterizing Split Graphs 149

3.Degree Sequences and Split Graphs 152

Exercises 155

Bibliography 156

CHAPTER 7 Permutation Graphs 157

1.Introduction 157

2.Characterizing Permutation Graphs 158

3.Permutation Labelings 160

4.Applications 162

5.Sorting a Permutation Using Queues in Parallel 164

Exercises 168

Bibliography 169

CHAPTER 8 Interal Graphs 171

1.How It All Started 171

2.Some Characterizations of Interval Graphs 172

3.The Complexity of Consecutive l’s Testing 175

4.Applications of Interval Graphs 181

5.Preference and Indifference 185

6.Circular-Arc Graphs 188

Exercises 193

Bibliography 197

CHAPTER 9 Superperfect Graphs 203

1.Coloring Weighted Graphs 203

2.Superperfection 206

3.An Infinite Class of Superperfect Noncom parability Graphs 209

4.When Does Superperfect Equal Comparability？ 212

5.Composition of Superperfect Graphs 214

6.A Representation Using the Consecutive l’s Property 215

Exercises 218

Bibliography 218

CHAPTER 10 Threshold Graphs 219

1.The Threshold Dimension 219

2.Degree Partition of Threshold Graphs 223

3.A Characterization Using Permutations 227

4.An Application to Synchronizing Parallel Processes 229

Exercises 231

Bibliography 234

CHAPTER 11 Not So Perfect Graphs 235

1.Sorting a Permutation Using Stacks in Parallel 235

2.Intersecting Chords of a Circle 237

3.Overlap Graphs 242

4.Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs 244

5.A Graph Theoretic Characterization of Overlap Graphs 248

Exercises 251

Bibliography 253

CHAPTER 12 Perfect Gaussian Elimination 254

1.Perfect Elimination Matrices 254

2.Symmetric Matrices 256

3.Perfect Elimination Bipartite Graphs 259

4.Chordal Bipartite Graphs 261

Exercises 264

Bibliography 266

Appendix 269

A.A Small Collection of NP-Complete Problems 269

B.An Algorithm for Set Union， Intersection，Difference， and Symmetric Difference of Two Subsets 270

C.Topological Sorting： An Example of Algorithm 2.4 271

D.An Illustration of the Decomposition Algorithm 273

E.The Properties P.E.B.， C.B.，（P.E.B.）’，（C.B.）’ Illustrated 273

F.The Properties C， C —， T， T — llustrated 275

Epilogue 2004 277

Index 307