Exact bipartite crossing minimization under tree constraints

Beitrag in einem Sammelwerk

Details zur Publikation

Autorinnen und Autoren: Baumann F, Buchheim C, Liers F
Herausgeber: Paola Festa
Titel Sammelwerk: Experimental Algorithms
Verlag: Springer
Verlagsort: Berlin, Heidelberg
Jahr der Veröffentlichung: 2010
Titel der Reihe: Lecture Notes in Computer Science
Band: 6049
Seitenbereich: 118-128
ISBN: 9783642131929


A tanglegram consists of a pair of (not necessarily binary) trees. Additional edges, called tangles, may connect the leaves of the first with those of the second tree. The task is to draw a tanglegram with a minimum number of tangle crossings while making sure that the trees are drawn crossing-free. This problem has relevant applications in computational biology, e.g., for the comparison of phylogenetic trees. Most existing approaches are only applicable for binary trees. In this work, we show that the problem can be formulated as a quadratic linear ordering problem (QLO) with side constraints. Buchheim et al. (INFORMS J. Computing, to appear) showed that, appropriately reformulated, the QLO polytope is a face of some cut polytope. It turns out that the additional side constraints do not destroy this property. Therefore, any polyhedral approach to max-cut can be used in our context. We present experimental results for drawing random and real-world tanglegrams defined on both binary and general trees. We evaluate linear as well as semidefinite programming techniques. By extensive experiments, we show that our approach is very efficient in practice. © Springer-Verlag Berlin Heidelberg 2010.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Technische Universität Dortmund
Universität zu Köln


Baumann, F., Buchheim, C., & Liers, F. (2010). Exact bipartite crossing minimization under tree constraints. In Paola Festa (Eds.), Experimental Algorithms. (pp. 118-128). Berlin, Heidelberg: Springer.

Baumann, Frank, Christoph Buchheim, and Frauke Liers. "Exact bipartite crossing minimization under tree constraints." Experimental Algorithms. Ed. Paola Festa, Berlin, Heidelberg: Springer, 2010. 118-128.


Zuletzt aktualisiert 2018-23-10 um 14:53