Computer Science/Discrete Mathematics Seminar I

The local ratio framework introduced by Bar Yehuda and Evan in 1981 provides a unified framework for many approximation algorithms. Recently, the local ratio technique has been used to provide efficient approximation algorithms for a number of packing problems. Motivated by these recent algorithms, Akcoglu, Aspnes, DasGupta and Kao suggested a new class of graphs extending the class of chordal graphs. Namely, "sequential k-independent graphs" generalize the concept of a perfect elimination ordering by allowing the "local neighborhood'' of each vertex in the ordering to have independence number k. We study this class of graphs and show how various graph problems can be efficiently approximated by conceptually simple combinatorial algorithms. We also compare this new graph class to other known classes of graphs For example, planar graphs are sequentially 3-independent. Sequential k-independent graphs are another example of the more general concept of sequential elimimation graphs.The results in this talk are based on work with Yuli Ye.