Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Tuesday, October 4, 2005 Time: 2:30 PM Place: MC5136         Title: An asymptotic approximation scheme for multigraph edge coloring Speaker: Peter Sanders, Karlsruhe University Abstract:   We present a polynomial time algorithm that colors the edges of a multigraph (parallel edges allowed) such that no two edges incident to the same node have the same color. The number of colors used is optimal up to an ADDITIVE, sublinear term. The best previously known algorithm needed more then 11/10 times the optimal number of colors in some cases.