Speaker: Yuli Ye
Department of Computer Science, University of Toronto
Title: Elimination Structures in Graphs
A graph is chordal if it does not contain any induced cycle of size greater than three. An alternative characterization of chordal graphs
is via a perfect elimination ordering, which is an ordering of the
vertices such that, for each vertex v, the neighbors of v that
occur later than v in the ordering form a clique.
We study graph classes based on an extension of the perfect
elimination ordering. We show various graph problems can be
efficiently approximated by conceptually simple combinatorial
algorithms, and furthermore, many natural graph classes fall into this
general framework with small parameters. Our generalized formulation
unifies and extends several previously known results.
This is joint work with Allan Borodin.