> Detailanzeige

Jünger, Michael [VerfasserIn]; Mutzel, Petra [VerfasserIn]

2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel
  • Titel: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
  • Beteiligte: Jünger, Michael [VerfasserIn]; Mutzel, Petra [VerfasserIn]
  • Erschienen: Brown Univ., 1997
  • Sprache: Deutsch; Englisch
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.