LEADER 04629nam 2200577 450 001 9910786640403321 005 20230120014728.0 010 $a1-4832-7197-8 035 $a(CKB)3710000000200668 035 $a(EBL)1888440 035 $a(SSID)ssj0001454760 035 $a(PQKBManifestationID)11792480 035 $a(PQKBTitleCode)TC0001454760 035 $a(PQKBWorkID)11498255 035 $a(PQKB)11088429 035 $a(MiAaPQ)EBC1888440 035 $a(EXLCZ)993710000000200668 100 $a20150112h19801980 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithmic graph theory and perfect graphs /$fMartin Charles Golumbic 210 1$aNew York, New York ;$aLondon, England :$cAcademic Press,$d1980. 210 4$dİ1980 215 $a1 online resource (307 p.) 225 1 $aComputer Science and Applied Mathematics 300 $aDescription based upon print version of record. 311 $a1-322-47765-5 311 $a0-12-289260-7 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aFront Cover; Algorithmic Graph Theory and Perfect Graphs; Copyright Page; Dedication; Table of Contents; 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 327 $a1. The Star of the Show2. 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 327 $a7. Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated GraphsExercises; 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 327 $a1. An Introduction to Chapters 6-8: Interval, Permutation, and Split Graphs2. 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 327 $a6. Circular-Arc GraphsExercises; 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 327 $aChapter 11. Not So Perfect Graphs 330 $aAlgorithmic Graph Theory and Perfect Graphs 410 0$aComputer science and applied mathematics. 606 $aPerfect graphs 615 0$aPerfect graphs. 676 $a511/.5 700 $aGolumbic$b Martin Charles$0104097 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910786640403321 996 $aAlgorithmic graph theory and perfect graphs$9437139 997 $aUNINA