• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Kernel and Fast Algorithm for Dense Triplet Inconsistency
【24h】

Kernel and Fast Algorithm for Dense Triplet Inconsistency

机译：密集三重态不一致的内核和快速算法

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

摘要

We study the parameterized complexity of inferring su-pertrees from sets of rooted triplets, an important problem in phylo-genetics. For a set L of labels and a dense set R of triplets distinctly leaf-labeled by 3-subsets of L we seek a tree distinctly leaf-labeled by L and containing all but at most p triplets from R as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O(p2) labels, and a subexponential fixed-parameter algorithm running in time 2~O(p~(1/3)log p)+O(n~4).
机译：我们研究了从有根的三胞胎的集合推断超树的参数化复杂性，这是系统遗传学中的一个重要问题。对于一组L的标签和一组由L的3个子集明显标记为叶子的三胞胎的密集组R，我们寻求一棵由L明显标记为叶子的树，该树包含来自R的所有（最多p个）三胞胎为同胚亚树。我们的结果是针对此问题的第一个多项式内核，带有O（p2）标签，以及次指数固定参数算法在2〜O（p〜（1/3）log p）+ O（n〜4）的时间运行。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号