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.
-
- 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
BibTeX
@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},
}