Universität zu Köln

Speckenmeyer, Ewald, Wotzlaw, Andreas and Porschen, Stefan (2011). A Satisfiability-based Approach for Embedding Generalized Tanglegrams on Level Graphs. In: Theory and Applications of Satisfiability Testing - SAT 2011 : 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings, pp. 134-144. Springer.

Preview

PDF zaik2011-614.pdf Download (299kB) | Preview

Abstract

A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this paper we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as planar embedding and the second as crossing minimization problem. We show that our satisfiability formulation of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED Wotzlaw, Andreas UNSPECIFIED UNSPECIFIED UNSPECIFIED Porschen, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550072
Title of Book:	Theory and Applications of Satisfiability Testing - SAT 2011 : 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings
Series Name:	Lecture notes in computer science
Volume:	6695
Page Range:	pp. 134-144
Date:	February 2011
Publisher:	Springer
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/55007