MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Evaluating a 2-approximation algorithm for edge-separators in planar graphs

Garg, Naveen and Manss, Christian

March 1997, 9 pages.

Status: available - back from printing

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.

  • Attachement: (106 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Garg, Naveen and Manss, Christian},
  TITLE = {Evaluating a 2-approximation algorithm for edge-separators in planar graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-010},
  MONTH = {March},
  YEAR = {1997},
  ISSN = {0946-011X},