Algorithmic Graph Theory and Perfect GraphsGraph theoretic foundations; The design of efficient algorithms; Perfect graphs; Triangulated graphs; Comparability graphs; Spit graphs; Permutation graphs; Interval graphs; Superperfect graphs; Thereshold graphs; Not so perfect graphs; Perfect gaussian elimination. |
Other editions - View all
Common terms and phrases
A₁ acyclic Adj(v adjacency sets algorithm arcs assume B₁ bipartite graph Chapter characterization chordless chordless cycle chords circular-arc graph clique cover clique matrix clique of G color classes Combinatorics comparability graph complete graph consecutive 1's Corollary corresponding cycle data structure decomposition defined denote derived graph dimension Discrete Math endpoint equivalent exists Fulkerson graph G graph in Figure Graph Theory implication class implies induced subgraph integer intersection graph interval graph isomorphic labeling Lemma Let G linear M₁ maximum clique maximum stable set NP-complete obtain orientation of G p-critical graph P₁ partially ordered sets partition permutation graph posets PQ-tree problem Proof queue satisfies Section semiorder sequence set of G simplex split graph stable set subset subtrees superperfect Theorem threshold graph transitive orientation tree triangulated graph undirected graph Univ v₁ vertex of G vertices