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

Jünger, Michael; Mutzel, Petra

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

このアイテムの新しいバージョンが利用可能です:
https://pure.mpg.de/pubman/item/item_1825072_4

詳細要約

前へ次へ / 9110

公開

報告書

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

MPS-Authors

/persons/resource/persons45092

Mutzel, Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

1996-1-025
(全文テキスト（全般）), 10KB

付随資料 (公開)

There is no public supplementary material available

引用

Jünger, M., & Mutzel, P.(1996). 2-Layer straigthline crossing minimization: performance of exact and heuristic algorithms (MPI-I-1996-1-025). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-A040-6

要旨

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.