Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

by Martin Charles Golumbic
Released February 2004
Publisher(s): North Holland
ISBN: 9780080526966

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright page
  5. Dedication
  6. Foreword 2004: The annals edition
    1. Publisher Summary
  7. Foreword
    1. Publisher Summary
  8. Preface
    1. Publisher Summary
  9. Acknowledgments
  10. List of symbols
  11. Corrections and errata to: Algorithmic graph theory and perfect graphs, the original 1980 edition
  12. Chapter 1: Graph Theoretic Foundations
    1. Publisher Summary
    2. 1 Basic Definitions and Notations
    3. 2 Intersection Graphs
    4. 3 Interval Graphs—A Sneak Preview of the Notions Coming Up
    5. 4 Summary
    6. EXERCISES
  13. Chapter 2: The Design of Efficient Algorithms
    1. Publisher Summary
    2. 1 The Complexity of Computer Algorithms
    3. Summary
    4. 2 Data Structures
    5. 3 How to Explore a Graph
    6. 4 Transitive Tournaments and Topological Sorting
    7. Exercises
  14. Chapter 3: Perfect graphs
    1. Publisher Summary
    2. 1 The Star of the Show
    3. THE PERFECT GRAPH
    4. 2 The Perfect Graph Theorem
    5. 3 p-Critical and Partitionable Graphs*
    6. 4 A Polyhedral Characterization of Perfect Graphs
    7. 5 A Polyhedral Characterization of p-Critical Graphs
    8. 6 The Strong Perfect Graph Conjecture
    9. Exercises
  15. Chapter 4: Triangulated graphs
    1. Publisher Summary
    2. 1 Introduction
    3. 2 Characterizing Triangulated Graphs
    4. 3 Recognizing Triangulated Graphs by Lexicographic Breadth-First Search
    5. 4 The Complexity of Recognizing Triangulated Graphs
    6. 5 Triangulated Graphs as Intersection Graphs
    7. 6 Triangulated Graphs Are Perfect
    8. 7 Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated Graphs
    9. EXERCISES
  16. Chapter 5: Comparability graphs
    1. Publisher Summary
    2. 1 Γ-Chains and Implication Classes
    3. 2 Uniquely Partially Orderable Graphs
    4. 3 The Number of Transitive Orientations
    5. 4 Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations
    6. 5 The Γ*-Matroid of a Graph
    7. 6 The Complexity of Comparability Graph Recognition
    8. 7 Coloring and Other Problems on Comparability Graphs
    9. 8 The Dimension of Partial Orders
    10. Exercises
  17. Chapter 6: Split graphs
    1. Publisher Summary
    2. 1 An Introduction to Chapters 6–8:Interval, Permutation, and Split Graphs
    3. 2 Characterizing Split Graphs
    4. 3 Degree Sequences and Split Graphs
    5. Theorem 6.4 (Havel [1955], Hakimi [1962])
    6. EXERCISES
  18. Chapter 7: Permutation graphs
    1. Publisher Summary
    2. 1 Introduction
    3. 2 Characterizing Permutation Graphs
    4. 3 Permutation Labelings
    5. 4 Applications
    6. 5 Sorting a Permutation Using Queues in Parallel
    7. Exercises
  19. Chapter 8: Interval graphs
    1. Publisher Summary
    2. 1 How It All Started
    3. 2 Some Characterizations of Interval Graphs
    4. 3 The Complexity of Consecutive 1’s Testing
    5. 4 Applications of Interval Graphs
    6. 5 Preference and Indifference
    7. 6 Circular-Arc Graphs
    8. Exercises*
  20. Chapter 9: Superperfect graphs
    1. Publisher Summary
    2. 1 Coloring Weighted Graphs
    3. 2 Superperfection
    4. 3 An Infinite Class of Superperfect Noncomparability Graphs
    5. 4 When Does Superperfect Equal Comparability?
    6. 5 Composition of Superperfect Graphs
    7. 6 A Representation Using the Consecutive 1’s Property
    8. Exercises
  21. Chapter 10: Threshold graphs
    1. Publisher Summary
    2. 1 The Threshold Dimension
    3. 2 Degree Partition of Threshold Graphs
    4. 3 A Characterization Using Permutations
    5. 4 An Application to Synchronizing Parallel Processes
    6. Exercises
  22. Chapter 11: Not So Perfect Graphs
    1. Publisher Summary
    2. 1 Sorting a Permutation Using Stacks in Parallel
    3. 2 Intersecting Chords of a Circle
    4. 3 Overlap Graphs
    5. 4 Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs
    6. 5 A Graph Theoretic Characterization of Overlap Graphs
    7. EXERCISES
  23. Chapter 12: Perfect Gaussian Elimination
    1. Publisher Summary
    2. 1 Perfect Elimination Matrices
    3. 2 Symmetric Matrices
    4. 3 Perfect Elimination Bipartite Graphs
    5. 4 Chordal Bipartite Graphs
    6. Summary
    7. EXERCISES
  24. Appendix
  25. Epilogue 2004
  26. Index

Product information

  • Title: Algorithmic Graph Theory and Perfect Graphs, 2nd Edition
  • Author(s): Martin Charles Golumbic
  • Release date: February 2004
  • Publisher(s): North Holland
  • ISBN: 9780080526966