MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments

MPI-I-97-1-010

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.

  • MPI-I-97-1-010.ps
  • Attachement: MPI-I-97-1-010.ps (106 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-010

Hide details for BibTeXBibTeX
@TECHREPORT{GargManss97,
  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},
}