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 NP-hard problems. Hopefully we shall have time to touch upon
approximation algorithms, fixed parameter algorithms, rigorous analysis of
heuristics, and also on some negative results. |