Universität zu Köln

Wotzlaw, Andreas, Speckenmeyer, Ewald and Porschen, Stefan (2012). Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation. Discret Appl. Math., 160 (16-17). S. 2349 - 2364. AMSTERDAM: ELSEVIER. ISSN 1872-6771

Full text not available from this repository.

Abstract

A tanglegram is a pair of (not necessarily binary) 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 work we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as the planar embedding and the second as the crossing minimization problem. We show that our satisfiability-based encoding 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. Furthermore, we present an experimental comparison of our technique and several known heuristics for solving generalized binary tanglegrams, showing its competitive performance and efficiency and thus proving its practical usability. (C) 2012 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Wotzlaw, Andreas UNSPECIFIED UNSPECIFIED UNSPECIFIED Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED Porschen, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-480775
DOI:	10.1016/j.dam.2012.05.028
Journal or Publication Title:	Discret Appl. Math.
Volume:	160
Number:	16-17
Page Range:	S. 2349 - 2364
Date:	2012
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-6771
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TREES Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/48077