Algorithmic Graph Theory and Perfect GraphsAlgorithmic 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. |
Contents
| 1 | |
Chapter 2 The Design of Efficient Algorithms | 22 |
Chapter 3 Perfect Graphs | 51 |
Chapter 4 Triangulated Graphs | 81 |
Chapter 5 Comparability Graphs | 105 |
Chapter 6 Split Graphs | 149 |
Chapter 7 Permutation Graphs | 157 |
Chapter 8 Interval Graphs | 171 |
Other editions - View all
Common terms and phrases
Adj(v Adj(x adjacency sets algorithm arcs assume called Chapter characteristic vector characterization chordless cycle chords circle circular-arc graph clique cover clique matrix clique of G color classes Combinatorics comparability graph complement complete graph consecutive 1's property Corollary corresponding data structure decomposition defined denote derived graph dimension Discrete Math disjoint endpoint equivalent example exists G contains Golumbic graph G graph in Figure Graph Theory implication class implies induced subgraph integer intersection graph interval graph isomorphic labeling Lemma Let G linear maximum clique maximum stable set n x n NP-complete obtain orientation of G partially ordered sets partition path perfect elimination scheme permutation graph posets PQ-tree problem Proof Prove the following queue representation satisfies Section semiorder sequence set of G simplex simplicial split graph subset superperfect Theorem threshold graph topological sorting transitive orientation tree triangulated graph undirected graph Univ vertices of G