Universität zu Köln

Baumann, Frank, Buchheim, Christoph ORCID: 0000-0001-9974-404X and Liers, Frauke (2010). Exact Bipartite Crossing Minimization under Tree Constraints. In: 9th International Symposium on Experimental Algorithms SEA 2010, pp. 118-128. Springer Verlag.

Preview

PDF zaik2009-581.pdf - Draft Version Download (138kB) | Preview

Abstract

A tanglegram consists of a pair of (not necessarily binary) trees T_1, T_2 with leaf sets L_1, L_2. Additional edges, called tangles, may connect nodes in L_1 with those in L_2. The task is to draw the tanglegram with a minimum number of tangle edge crossings while making sure that no crossing occurs between edges within each tree. This problem has relevant applications in computational biology, e.g., for the comparison of phylogenetic trees. In this work, we show that the problem can be formulated as a quadratic linear ordering problem (QLO) with additional side constraints. It was already shown that, appropriately reformulated, the QLO polytope is a face of some cut polytope. It turns out that the additional side constraints arising in our application 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 realistic tanglegrams using both linear and semidefinite programming techniques, showing that our approach is very efficient in practice.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Baumann, Frank UNSPECIFIED UNSPECIFIED UNSPECIFIED Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549818
Title of Book:	9th International Symposium on Experimental Algorithms SEA 2010
Series Name:	Lecture Notes in Computer Science
Volume:	6049
Page Range:	pp. 118-128
Date:	2010
Publisher:	Springer Verlag
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54981