Algorithmic Graph Theory and Perfect Graphs: Second Edition
Regular price
37.500 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Contentsvii
- Foreword 2004xiii
- Forewordxv
- Prefacexvii
- Acknowledgmentsxix
- List of Symbolsxxi
- Corrections and Errataxxiii
- Chapter 1. Graph Theoretic Foundations1
- 1. Basic Definitions and Notations1
- 2. Intersection Graphs9
- 3. Interval Graphs„A Sneak Preview of the Notions Coming Up13
- 4. Summary17
- Exercises18
- Bibliography20
- Chapter 2. The Design of Efficient Algorithms22
- 1. The Complexity of Computer Algorithms22
- 2. Data Structures31
- 3. How to Explore a Graph37
- 4. Transitive Tournaments and Topological Sorting42
- Exercises45
- Bibliography48
- Chapter 3. Perfect Graphs51
- 1. The Star of the Show51
- 2. The Perfect Graph Theorem53
- 3. p-Critical and Partitionable Graphs58
- 4. A Polyhedral Characterization of Perfect Graphs62
- 5. A Polyhedral Characterization of p-Critical Graphs65
- 6. The Strong Perfect Graph Conjecture71
- Exercises75
- Bibliography77
- Chapter 4. Triangulated Graphs81
- 1. Introduction81
- 2. Characterizing Triangulated Graphs81
- 3. Recognizing Triangulated Graphs by Lexicographic Breadth-First Search84
- 4. The Complexity of Recognizing Triangulated Graphs87
- 5. Triangulated Graphs as Intersection Graphs91
- 6. Triangulated Graphs Are Perfect94
- 7. Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated G98
- Exercises100
- Bibliography102
- Chapter 5. Comparability Graphs105
- 1. Γ-Chains and Implication Classes105
- 2. Uniquely Partially Orderable Graphs109
- 3. The Number of Transitive Orientations113
- 4. Schemes and G-Decompositions„An Algorithm for Assigning Transitive Orientations120
- 5. The Γ*-Matroid of a Graph124
- 6. The Complexity of Comparability Graph Recognition129
- 7. Coloring and Other Problems on Comparability Graphs132
- 8. The Dimension of Partial Orders135
- Exercises139
- Bibliography142
- Chapter 6. Split Graphs149
- 1. An Introduction to Chapters 6–8 : Interval, Permutation, and Split Graphs149
- 2. Characterizing Split Graphs149
- 3. Degree Sequences and Split Graphs152
- Exercises155
- Bibliography156
- Chapter 7. Permutation Graphs157
- 1. Introduction157
- 2. Characterizing Permutation Graphs158
- 3. Permutation Labelings160
- 4. Applications162
- 5. Sorting a Permutation Using Queues in Parallel164
- Exercises168
- Bibliography169
- Chapter 8. Interval Graphs171
- 1. How It All Started171
- 2. Some Characterizations of Interval Graphs172
- 3. The Complexity of Consecutive 1’s Testing175
- 4. Applications of Interval Graphs181
- 5. Preference and Indifference185
- 6. Circular- Arc Graphs188
- Exercises193
- Bibliography197
- Chapter 9. Superperfect Graphs203
- 1. Coloring Weighted Graphs203
- 2. Superperfection206
- 3. An Infinite Class of Superperfect Noncomparability Graphs209
- 4. When Does Superperfect Equal Comparability?212
- 5. Composition of Superperfect Graphs214
- 6. A Representation Using the Consecutive 1’s Property215
- Exercises218
- Bibliography218
- Chapter 10. Threshold Graphs219
- 1. The Threshold Dimension219
- 2. Degree Partition of Threshold Graphs223
- 3. A Characterization Using Permutations227
- 4. An Application to Synchronizing Parallel Processes229
- Exercises231
- Bibliography234
- Chapter 11. Not So Perfect Graphs235
- 1. Sorting a Permutation Using Stacks in Parallel235
- 2. Intersecting Chords of a Circle237
- 3. Overlap Graphs242
- 4. Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs244
- 5. A Graph Theoretic Characterization of Overlap Graphs248
- Exercises251
- Bibliography253
- Chapter 12. Perfect Gaussian Elimination254
- 1. Perfect Elimination Matrices254
- 2. Symmetric Matrices256
- 3. Perfect Elimination Bipartite Graphs259
- 4. Chordal Bipartite Graphs261
- Exercises265
- Bibliography267
- Appendix269
- A. A Small Collection of NP-complete Problems269
- B. An Algorithm for Set Union, Intersection, Difference, and Symmetric Difference of Two Subsets270
- C. Topological Sorting: An Example of Algorithm 2.4271
- D. An Illustration of the Decomposition Algorithm273
- E. The Properties P.E.B., C.B., (P.E.B.)', (C .B.) ' Illustrated273
- F. The Properties C, C, T, T Illustrated275
- Epilogue 2004277
- Index307
Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails.
The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition.
· New edition of the "Classic" book on the topic
· Wonderful introduction to a rich research area
· Leading author in the field of algorithmic graph theory
· Beautifully written for the new mathematician or computer scientist
· Comprehensive treatment
The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition.
· New edition of the "Classic" book on the topic
· Wonderful introduction to a rich research area
· Leading author in the field of algorithmic graph theory
· Beautifully written for the new mathematician or computer scientist
· Comprehensive treatment