Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-97-1-010

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

Garg, Naveen and Manss, Christian

MPI-I-97-1-010. March 1997, 9 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:


To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-010.ps106 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://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},
}