hide
Free keywords:
-
Abstract:
In this paper we report on results obtained by an implementation of a
2-approximation algorithm for edge separators in planar
graphs. For 374 out of the 435 instances the algorithm returned the optimum
solution. For the remaining instances the solution returned was never more
than 10.6\% away from the lower bound on the optimum separator. We also
improve the worst-case running time of the algorithm from $O(n^6)$ to $O(n^5)$
and present techniques which improve the running time significantly in
practice.
