...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
【24h】

The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

机译：构造包含或避免给定子树的叶子标签树的难度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given a set of trees with leaves labelled from a set L, is there a tree T with leaves labelled by L such that each of the given trees is homeomorphic to a subtree of T? This question is known to be NP-complete in general, but solvable in polynomial time if all the given trees have one label in common (equivalently, if the given trees are rooted). Here we show that this problem is NP-complete even if there are two labels x and y such that each given tree contains x or y. However, if it is known that the distance between x and y is less than 4, then the problem is solvable in polynomial time. We give an algorithm for doing this. On the other hand, we show that the question of whether a fully resolved (binary) tree exists which has no subtree homeomorphic to one of the given ones is NP-complete, even when the given trees are rooted. This sheds some light on the complexity of determining whether a probability assignment to trees is coherent. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 6]
机译：给定具有从集合L标记叶子的树的集合，是否有一棵树T的叶子被L标记，从而每个给定的树对T的子树是同胚的？众所周知，这个问题通常是NP完全的，但是如果所有给定的树都具有一个共同的标号（等效于给定的树是根），则可以在多项式时间内解决。在这里我们表明，即使存在两个标签x和y使得每个给定的树包含x或y，这个问题也是NP完全的。但是，如果已知x和y之间的距离小于4，则该问题可以在多项式时间内解决。我们给出了执行此操作的算法。另一方面，我们表明，即使存在给定树的根，是否存在完全解析的（二叉树）问题也没有NP对给定树之一同胚的问题。这为确定确定树的概率分配是否一致的复杂性提供了一些启示。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：6]

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号