Thursday, November 10, 2005 



Finding Small Balanced Separators in Graphs 

In this
talk we present some algorithms that may be used in order to find small
balanced separators in graphs. More generally, this will illustrate some of
the approaches that are used by the "theory of computing" community when
dealing with NPhard problems. Hopefully we shall have time to touch upon
approximation algorithms, fixed parameter algorithms, rigorous analysis of
heuristics, and also on some negative results. 