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


2-Layer straigthline crossing minimization: performance of exact and heuristic algorithms

Jünger, Michael and Mutzel, Petra

MPI-I-96-1-025. October 1996, 14 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We present algorithms for the two layer straightline crossing
minimization problem that are able to compute exact optima. Our
computational results lead us to the conclusion that there is no
need for heuristics if one layer is fixed, even though the problem
is NP-hard, and that for the general problem with two variable layers,
true optima can be computed for sparse instances in which the smaller
layer contains up to 15 nodes. For bigger instances, the iterated
barycenter method turns out to be the method of choice among several
popular heuristics whose performance we could assess by comparing the
results to optimum solutions.
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-96-1-025.ps155 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:
Hide details for BibTeXBibTeX
  AUTHOR = {J{\"u}nger, Michael and Mutzel, Petra},
  TITLE = {2-Layer straigthline crossing minimization: performance of exact and heuristic algorithms},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-025},
  MONTH = {October},
  YEAR = {1996},
  ISSN = {0946-011X},