3 Credit Hour Course
Intended For Level 0 Term 0 Students
Prerequisite:
Vertex Orderings: st-Numbering and Canonical Orderings; Graph Decompositions and Their Algorithmic Applications: Ear Decomposition, Canonical Decomposition, Tree Decomposition, Path Width and Tree Width, PQ-tree, SPQR-tree, Split Decomposition, Recursively Decomposable Graphs, Clique Separator Decomposition; Graph Representations: Implicit Representations, Intersection and Containment Representations; Graph Classes Defined by Forbidden Subgraphs; Graph Classes Defined by Elimination Schemes; Classes of Graphs with Bounded Treewidth and Their Algorithmic Implications; Characterization, Construction and Recognition Algorithms for Some Special Classes of Graphs.
