
Algorithmic Graph Theory and Perfect Graphs
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Previous edition

Content
- Cover
- Algorithmic Graph Theory and Perfect Graphs
- Copyright
- Dedication
- Contents
- Foreword 2004
- Foreword
- Preface
- Acknowledgments
- List of Symbols
- Corrections and Errata
- 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. G-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 G*-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
- Epilogue 2004
- Index
System requirements
File format: ePUB
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use a reading software that can process the file format ePUB: e.g., Adobe Digital Editions or FBReader – both free (see eBook Help).
- Tablet/Smartphone (Android; iOS): Before downloading, install the free app Adobe Digital Editions (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (not Kindle).
The file format ePUB works well for novels and non-fiction books – i.e., „flowing” text without complex layout. On an e-reader or smartphone, line and page breaks automatically adjust to fit the small displays.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.