| Autor: |
Nöllenburg, Martin, Holten, Danny, Völker, Markus, Wolff, Alexander |
| Rok vydání: |
2008 |
| Předmět: |
|
| Zdroj: |
Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 106-119. SIAM, April 2009 |
| Druh dokumentu: |
Working Paper |
| Popis: |
A binary tanglegram is a pair of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics or software engineering, it is required that the individual trees are drawn crossing-free. A natural optimization problem, denoted tanglegram layout problem, is thus to minimize the number of crossings between inter-tree edges. The tanglegram layout problem is NP-hard and is currently considered both in application domains and theory. In this paper we present an experimental comparison of a recursive algorithm of Buchin et al., our variant of their algorithm, the algorithm hierarchy sort of Holten and van Wijk, and an integer quadratic program that yields optimal solutions.
Comment: see http://www.siam.org/proceedings/alenex/2009/alx09_011_nollenburgm.pdf |
| Databáze: |
arXiv |
| Externí odkaz: |
|
