Algorithmic Graph Theory and Perfect Graphs
- 1st Edition - March 28, 1980
- Imprint: Academic Press
- Author: Martin Charles Golumbic
- Editor: Werner Rheinboldt
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 3 9 5 5 - 2
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 7 1 9 7 - 2
Algorithmic Graph Theory and Perfect Graphs provides an introduction to graph theory through practical problems. This book presents the mathematical and algorithmic properties of… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteAlgorithmic Graph Theory and Perfect Graphs provides an introduction to graph theory through practical problems. This book presents the mathematical and algorithmic properties of special classes of perfect graphs. Organized into 12 chapters, this book begins with an overview of the graph theoretic notions and the algorithmic design. This text then examines the complexity analysis of computer algorithm and explains the differences between computability and computational complexity. Other chapters consider the parameters and properties of a perfect graph and explore the class of perfect graphs known as comparability graph or transitively orientable graphs. This book discusses as well the two characterizations of triangulated graphs, one algorithmic and the other graph theoretic. The final chapter deals with the method of performing Gaussian elimination on a sparse matrix wherein an arbitrary choice of pivots may result in the filling of some zero positions with nonzeros. This book is a valuable resource for mathematicians and computer scientists.
Foreword
Preface
Acknowledgments
List of Symbols
Chapter 1 Graph Theoretic Foundations
1. Basic Definitions and Notations
2. Intersection Graphs
3. Interval Graphs—A Sneak Preview of the Notions Coming Up
4. Summary
Exercises
Bibliography
Chapter 2 The Design of Efficient Algorithms
1. The Complexity of Computer Algorithms
2. Data Structures
3. How to Explore a Graph
4. Transitive Tournaments and Topological Sorting
Exercises
Bibliography
Chapter 3 Perfect Graphs
1. The Star of the Show
2. The Perfect Graph Theorem
3. p-Critical and Partitionable Graphs
4. A Polyhedral Characterization of Perfect Graphs
5. A Polyhedral Characterization of p-Critical Graphs
6. The Strong Perfect Graph Conjecture
Exercises
Bibliography
Chapter 4 Triangulated Graphs
1. Introduction
2. Characterizing Triangulated Graphs
3. Recognizing Triangulated Graphs by Lexicographic Breadth-First Search
4. The Complexity of Recognizing Triangulated Graphs
5. Triangulated Graphs as Intersection Graphs
6. Triangulated Graphs Are Perfect
7. Fast Algorithms for the Coloring, Clique, Stable Set, and Clique-Cover Problems on Triangulated Graphs
Exercises
Bibliography
Chapter 5 Comparability Graphs
1. Γ-Chains and Implication Classes
2. Uniquely Partially Orderable Graphs
3. The Number of Transitive Orientations
4. Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations
5. The Γ-Matroid of a Graph
6. The Complexity of Comparability Graph Recognition
7. Coloring and Other Problems on Comparability Graphs
8. The Dimension of Partial Orders
Exercises
Bibliography
Chapter 6 Split Graphs
1. An Introduction to Chapters 6-8: Interval,Permutation, and Split Graphs
2. Characterizing Split Graphs
3. Degree Sequences and Split Graphs
Exercises
Bibliography
Chapter 7 Permutation Graphs
1. Introduction
2. Characterizing Permutation Graphs
3. Permutation Labelings
4. Applications
5. Sorting a Permutation Using Queues in Parallel
Exercises
Bibliography
Chapter 8 Interval Graphs
1. How It All Started
2. Some Characterizations of Interval Graphs
3. The Complexity of Consecutive 1's Testing
4. Applications of Interval Graphs
5. Preference and Indifference
6. Circular-Arc Graphs
Exercises
Bibliography
Chapter 9 Superperfect Graphs
1. Coloring Weighted Graphs
2. Superperfection
3. An Infinite Class of Superperfect Noncomparability Graphs
4. When Does Superperfect Equal Comparability?
5. Composition of Superperfect Graphs
6. A Representation Using the Consecutive 1's Property
Exercises
Bibliography
Chapter 10 Threshold Graphs
1. The Threshold Dimension
2. Degree Partition of Threshold Graphs
3. A Characterization Using Permutations
4. An Application to Synchronizing Parallel Processes
Exercises
Bibliography
Chapter 11 Not So Perfect Graphs
1. Sorting a Permutation Using Stacks in Parallel
2. Intersecting Chords of a Circle
3. Overlap Graphs
4. Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs
5. A Graph Theoretic Characterization of Overlap Graphs
Exercises
Bibliography
Chapter 12 Perfect Gaussian Elimination
1. Perfect Elimination Matrices
2. Symmetric Matrices
3. Perfect Elimination Bipartite Graphs
4. Chordal Bipartite Graphs
Exercises
Bibliography
Appendix
A. A Small Collection of NP-Complete Problems
B. An Algorithm for Set Union, Intersection, Difference, and Symmetric Difference of Two Subsets
C. Topological Sorting: An Example of Algorithm 2.4
D. An Illustration of the Decomposition Algorithm
E. The Properties P.E.B., C.B., (P.E.B.)', (C.B.)' Illustrated
F. The Properties C, C, T, T Illustrated
Index
- Edition: 1
- Published: March 28, 1980
- Imprint: Academic Press
- No. of pages: 306
- Language: English
- Paperback ISBN: 9781483239552
- eBook ISBN: 9781483271972
Read Algorithmic Graph Theory and Perfect Graphs on ScienceDirect