Algorithmic graph theory and perfect graphs / Martin Charles Golumbic.
Series Computer science and applied mathematicsEditor: New York : Academic Press, 1980Descripción: xx, 284 p. : il. ; 24 cmISBN: 0122892607Tema(s): Perfect graphsOtra clasificación: 68E10 (05C99 68-01 68C05)Foreword xiii Preface xv Acknowledgments xvii List of Symbols xix chapter 1 Graph Theoretic Foundations 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 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 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 1. Introduction 8l 2. Characterizing Triangulated Graphs 8l 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 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 Γ*-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 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 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 Interval Graphs 1. How It All Started [171] 2. Some Characterizations of Interval Graphs [172] 3. The Complexity of Consecutive 1 '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 1. Coloring Weighted Graphs [203] 2. Superperfection [206] 3. An Infinite Class of Superperfect Noncomparability Graphs [209] 4. When Does Superperfect Equal Comparability? [212] 5. Composition of Superperfect Graphs [214] 6. A Representation Using the Consecutive 1 ’s Property [215] Exercises [218] Bibliography [218] chapter 10 Threshold Graphs 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 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 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 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 Illustrated [275] Index [277]
| Item type | Home library | Shelving location | Call number | Materials specified | Status | Date due | Barcode | Course reserves |
|---|---|---|---|---|---|---|---|---|
Libros
|
Instituto de Matemática, CONICET-UNS | Libros ordenados por tema | 68 G629 (Browse shelf) | Available | A-4995 |
Incluye referencias bibliográficas.
Foreword xiii --
Preface xv --
Acknowledgments xvii --
List of Symbols xix --
chapter 1 Graph Theoretic Foundations --
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 --
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 --
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 --
1. Introduction 8l --
2. Characterizing Triangulated Graphs 8l --
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 --
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 Γ*-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 --
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 --
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 Interval Graphs --
1. How It All Started [171] --
2. Some Characterizations of Interval Graphs [172] --
3. The Complexity of Consecutive 1 '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 --
1. Coloring Weighted Graphs [203] --
2. Superperfection [206] --
3. An Infinite Class of Superperfect Noncomparability Graphs [209] --
4. When Does Superperfect Equal Comparability? [212] --
5. Composition of Superperfect Graphs [214] --
6. A Representation Using the Consecutive 1 ’s Property [215] --
Exercises [218] --
Bibliography [218] --
chapter 10 Threshold Graphs --
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 --
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 --
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 --
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 Illustrated [275] --
Index [277] --
MR, 81e:68081
Click on an image to view it in the image viewer
There are no comments on this title.