Golumbic / Rheinboldt Algorithmic Graph Theory and Perfect Graphs

1. Auflage 2014
ISBN: 978-1-4832-7197-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 306 Seiten, Web PDF

Algorithmic 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.

Autoren/Hrsg.

Golumbic, Martin Charles

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Algorithmic Graph Theory and Perfect Graphs;4
3;Copyright Page;5
4;Table of Contents;8
5;Dedication;6
6;Foreword;14
7;Preface;16
8;Acknowledgments;18
9;List of Symbols;20
10;Chapter 1. Graph Theoretic Foundations ;22
10.1;1. Basic Definitions and Notations;22
10.2;2. Intersection Graphs;30
10.3;3. Interval Graphs—A Sneak Preview of the Notions Coming Up;34
10.4;4. Summary;38
10.5;Exercises;39
10.6;Bibliography;41
11;Chapter 2. The Design of Efficient Algorithms;43
11.1;1. The Complexity of Computer Algorithms;43
11.2;2. Data Structures;52
11.3;3. How to Explore a Graph;58
11.4;4. Transitive Tournaments and Topological Sorting;63
11.5;Exercises;66
11.6;Bibliography;69
12;Chapter 3. Perfect Graphs;72
12.1;1. The Star of the Show;72
12.2;2. The Perfect Graph Theorem;74
12.3;3. p-Critical and Partitionable Graphs;79
12.4;4. A Polyhedral Characterization of Perfect Graphs;83
12.5;5. A Polyhedral Characterization of p-Critical Graphs;86
12.6;6. The Strong Perfect Graph Conjecture;92
12.7;Exercises;96
12.8;Bibliography;98
13;Chapter 4. Triangulated Graphs;102
13.1;1. Introduction;102
13.2;2. Characterizing Triangulated Graphs;102
13.3;3. Recognizing Triangulated Graphs by Lexicographic Breadth-First Search;105
13.4;4. The Complexity of Recognizing Triangulated Graphs;108
13.5;5. Triangulated Graphs as Intersection Graphs;112
13.6;6. Triangulated Graphs Are Perfect;115
13.7;7. Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated Graphs;119
13.8;Exercises;121
13.9;Bibliography;123
14;Chapter 5. Comparability Graphs;126
14.1;1. G-Chains and Implication Classes;126
14.2;2. Uniquely Partially Orderable Graphs;130
14.3;3. The Number of Transitive Orientations;134
14.4;4. Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations;141
14.5;5. The G*-Matroid of a Graph;145
14.6;6. The Complexity of Comparability Graph Recognition;150
14.7;7. Coloring and Other Problems on Comparability Graphs;153
14.8;8. The Dimension of Partial Orders;156
14.9;Exercises;160
14.10;Bibliography;163
15;Chapter 6. Split Graphs;170
15.1;1. An Introduction to Chapters 6-8: Interval, Permutation, and Split Graphs;170
15.2;2. Characterizing Split Graphs;170
15.3;3. Degree Sequences and Split Graphs;173
15.4;Exercises;176
15.5;Bibliography;177
16;Chapter 7. Permutation Graphs;178
16.1;1. Introduction;178
16.2;2. Characterizing Permutation Graphs;179
16.3;3. Permutation Labelings;181
16.4;4. Applications;183
16.5;5. Sorting a Permutation Using Queues in Parallel;185
16.6;Exercises;189
16.7;Bibliography;190
17;Chapter 8. Interval Graphs;192
17.1;1. How It All Started;192
17.2;2. Some Characterizations of Interval Graphs;193
17.3;3. The Complexity of Consecutive 1's Testing;196
17.4;4. Applications of Interval Graphs;202
17.5;5. Preference and Indifference;206
17.6;6. Circular-Arc Graphs;209
17.7;Exercises;214
17.8;Bibliography;218
18;Chapter 9. Superperfect Graphs;224
18.1;1. Coloring Weighted Graphs;224
18.2;2. Superperfection;227
18.3;3. An Infinite Class of Superperfect Noncomparability Graphs;230
18.4;4. When Does Superperfect Equal Comparability?;233
18.5;5. Composition of Superperfect Graphs;235
18.6;6. A Representation Using the Consecutive 1's Property;236
18.7;Exercises;239
18.8;Bibliography;239
19;Chapter 10. Threshold Graphs;240
19.1;1. The Threshold Dimension;240
19.2;2. Degree Partition of Threshold Graphs;244
19.3;3. A Characterization Using Permutations;248
19.4;4. An Application to Synchronizing Parallel Processes;250
19.5;Exercises;252
19.6;Bibliography;255
20;Chapter 11. Not So Perfect Graphs;256
20.1;1. Sorting a Permutation Using Stacks in Parallel;256
20.2;2. Intersecting Chords of a Circle;258
20.3;3. Overlap Graphs;263
20.4;4. Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs;265
20.5;5. A Graph Theoretic Characterization of Overlap Graphs;269
20.6;Exercises;272
20.7;Bibliography;274
21;Chapter 12. Perfect Gaussian Elimination;275
21.1;1. Perfect Elimination Matrices;275
21.2;2. Symmetric Matrices;277
21.3;3. Perfect Elimination Bipartite Graphs;280
21.4;4. Chordal Bipartite Graphs;282
21.5;Exercises;285
21.6;Bibliography;287
22;Appendix;290
22.1;A. Small Collection of NP-Complete Problems;290
22.2;B. An Algorithm for Set Union, Intersection, Difference, and Symmetric Difference of Two Subsets;291
22.3;C. Topological Sorting: An Example of Algorithm 2.4;292
22.4;D. An Illustration of the Decomposition Algorithm;294
22.5;E. The Properties P.E.B., C.B., (P.E.B.)', (C.B.)' Illustrated;294
22.6;F. The Properties C, C, T, T Illustrated;296
23;Index;298