Name
Abstract | ||
|---|---|---|
A tanglegram is a pair of trees whose leaf sets are in one- to-one correspondence; matching leaves are connected by inter-tree edges. In applications such as phylogenetics or hierarchical clustering, 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 even for complete binary trees, for general binary trees the prob- lem is hard to approximate if the Unique Games Conjecture holds. In this paper we present an extensive experimen- tal comparison of a new and several known heuristics for the general binary case. We measure the performance of the heuristics with a simple integer linear program and a new ex- act branch-and-bound algorithm. The new heuristic returns the first solution that the branch-and-bound algorithm com- putes (in quadratic time). Surprisingly, in most cases this simple heuristic is at least as good as the best of the other heuristics. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/1.9781611972894.11 | algorithm engineering and experimentation |
Keywords | DocType | Volume |
binary tree,hierarchical clustering,branch and bound algorithm,optimization problem | Journal | abs/0806.0928 |
Citations | PageRank | References |
13 | 0.81 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Nöllenburg | 1 | 114 | 23.79 |
| Markus Völker | 2 | 54 | 5.78 |
| Alexander Wolff | 3 | 222 | 22.66 |
| Danny Holten | 4 | 1114 | 41.24 |