Comparing trees via crossing minimization
Comparing trees via crossing minimization
复制标题
DOI：
10.1016/j.jcss.2009.10.014
复制
发表时间：
2010-11-01
影响因子：
1.1
通讯作者：
Poths, Mathias
中科院分区：
文献类型：
--
作者：
Fernau, Henning;Kaufmann, Michael;Poths, Mathias
我们考虑以下在系统发育树的构建和评估中具有重要应用的问题（及其变体）：具有相同叶数的两个有根的无序二叉树必须嵌入平面的两个层中，以便叶在相邻的两个层中对齐。叶子之间的额外匹配边在不同树的叶子对之间提供了一对一的对应关系。我们的目标是找到两棵树的两个平面嵌入（绘制时没有交叉），使匹配边的交叉次数最小化。我们推导了（经典的）复杂性结果和（参数化的）算法来解决这个问题（及其一些变体）。(C) 2009 Elsevier Inc.版权所有。
We consider the following problem (and variants thereof) that has important applications in the construction and evaluation of phylogenetic trees: Two rooted unordered binary trees with the same number of leaves have to be embedded in two layers in the plane such that the leaves are aligned in two adjacent layers. Additional matching edges between the leaves give a one-to-one correspondence between pairs of leaves of the different trees. Our goal is to find two planar embeddings of the two trees (drawn without crossings) that minimize the number of crossings of the matching edges. We derive both (classical) complexity results and (parameterized) algorithms for this problem (and some variants thereof).(1) (C) 2009 Elsevier Inc. All rights reserved.