Algorithmic Graph Theory and Perfect Graphs

Martin Charles Golumbic (Eds.)978-0-444-51530-8, 0444515305

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

---

Table of contents :
Content:
Foreword 2004: The annals edition
Pages xiii-xiv
Martin Charles Golumbic

Foreword
Pages xv-xvi
Claude Berge

Preface
Pages xvii-xviii
Martin Charles Golumbic

Acknowledgments
Page xix

List of symbols
Pages xxi-xxii

Corrections and errata to: Algorithmic graph theory and perfect graphs, the original 1980 edition
Pages xxiii-xxvi

Chapter 1 Graph theoretic foundations Original Research Article
Pages 1-21

Chapter 2 The design of efficient algorithms Original Research Article
Pages 22-50

Chapter 3 Perfect graphs Original Research Article
Pages 51-80

Chapter 4 Triangulated graphs Original Research Article
Pages 81-104

Chapter 5 Comparability graphs Original Research Article
Pages 105-148

Chapter 6 Split graphs Original Research Article
Pages 149-156

Chapter 7 Permutation graphs Original Research Article
Pages 157-170

Chapter 8 Interval graphs Original Research Article
Pages 171-202

Chapter 9 Superperfect graphs Original Research Article
Pages 203-218

Chapter 10 Threshold graphs Original Research Article
Pages 219-234

Chapter 11 Not so perfect graphs Original Research Article
Pages 235-253

Chapter 12 Perfect gaussian elimination Original Research Article
Pages 254-267

Appendix
Pages 269-275

Epilogue 2004 Original Research Article
Pages 277-305

Index
Pages 307-314