On Star-Cover and Path-Cover of a Tree

机译：一棵树的星际和星际

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We study two restricted versions of the Subforest Isomorphism problem, the Star-Cover of a Tree (SCT) and the Path-Cover of A Tree (PCT) problems. Both problems are NP-complete. The problems are closely related to a number of well-studied problems, including the problems Subgraph Isomorphism, Tree Editing, and Graph Packing. We show that the problems SCT and PCT are fixed-parameter tractable. Thorough development of parameterized algorithms and kernelization algorithms for these problems are presented.

机译：我们研究了子森林同构问题的两个受限制的版本，即树的星际覆盖（SCT）和树的星际覆盖（PCT）问题。这两个问题都是NP完全的。这些问题与许多经过充分研究的问题密切相关，包括“子图同构”，“树编辑”和“图形打包”问题。我们表明问题SCT和PCT是固定参数可处理的。提出了针对这些问题的参数化算法和核化算法的全面开发。

著录项

来源
《International frontiers in algorithmics workshop》|2014年|298-308|共11页
会议地点
作者
Jie You; Qilong Feng; Jiong Guo; Feng Shi;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类
关键词

相似文献

外文文献
中文文献
专利

1. Size-growth relationship, tree spatial patterns, and tree-tree competition influence tree growth and stand complexity in a 160-year red pine chronosequence [J] . Looney Christopher E., DAmato Anthony W., Palik Brian J., Forest Ecology and Management . 2018,第期

机译：尺寸 - 生长关系，树空间模式和树木竞争影响树的增长并在160年的红松一致性中展望复杂性
2. Short Tree, Long Tree, Right Tree, Wrong Tree: New Acquisition Bias Corrections for Inferring SNP Phylogenies [J] . Leache Adam D., Banbury Barbara L., Felsenstein Joseph, Systematic Biology . 2015,第6期

机译：短树，长树，正确的树，错误的树：用于推断SNP系统发育的新采集偏差校正
3. Sacred fig trees promote frugivore visitation and tree seedlingTI Sacred fig trees promote frugivore visitation and tree seedling abundance in South India [J] . Caughlin TT, Ganesh T, Lowman MD Current Science: A Fortnightly Journal of Research . 2012,第6期

机译：无花果树促进果蝇走访和树木育苗TI印度无花果树促进果蝇走访和树木育苗
4. On Star-Cover and Path-Cover of a Tree [C] . Jie You, Qilong Feng, Jiong Guo, International Frontiers of Algorithmics Workshop . 2014

机译：在恒星和树的路径覆盖上
5. A Comparison of the Product Topology on Two Trees with the Tree Topology on the Concatenation of Two Trees [D] . Cox, Katlyn K. 2018

机译：两棵树的产品拓扑与两棵树串联的树拓扑的比较
6. Short Tree Long Tree Right Tree Wrong Tree: New Acquisition Bias Corrections for Inferring SNP Phylogenies [O] . Adam D. Leaché, Barbara L. Banbury, Joseph Felsenstein, -1

机译：短树长树正确的树错误的树：用于推断SNP系统发育的新采集偏差校正
7. Figure 6: (A) Tree resulted the standard MP analysis of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) constructed using the modified summary of Lehtonen et al. (2011) (see “Materials and Methods” for the details) and a posteriori rooted relatively Papio (length = 12,092, CI = 0.7877, RI = 0.5597); 34,022 characters are constant, and the number of the parsimony-informative characters is equal to 4,311. MP BS values are provided below branches. The only characters with non-ambiguous value of the outgroup (Papio) have been saved within concatenated alignment; (B) the average consensus tree of the score 0.00084 resulted the analysis of the Hennigian forest of the 5,507 trees derived from the binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see “Materials and Methods” for the details); Papio is assumed to be the best all-plesiomorphic group. “Additional…” FORESTER’s output tree file (see “Materials and Methods” for the details) selected for future analyses; (C) the average consensus tree of the score 0.00090 resulted the analysis of the Hennigian forest of the 5,339 trees derived from the modified binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see 6.I. and “Materials and Methods” for the details), but with all 168 trees, which contain the clade (Homo plus Pan) have been removed from the input forest. “Additional…” FORESTER’s output tree file (see “Materials and Methods”) selected for future analyses. [O] . -1

机译：图6：（A）树导致的标准MP分析的98-基因座的类人猿（人科，灵长类动物，哺乳动物），使用莱赫托宁等人的修改的摘要构成的超级矩阵。（2011）（参见细节“材料和方法”）以及相对植根狒狒后验概率（长度= 12092，CI = 0.7877，RI = 0.5597）; 34022个字符是恒定的，并且简约信息的字符数等于4311。下面提供分支MP BS值。与外类群（狒狒）的非模糊值的唯一的字符已被保存的级联对准内; （B）的得分0.00084的平均一致树导致从巨猿（原始人类，灵长类动物，哺乳动物）的98座超级矩阵的二进制表示获得的5507棵的Hennigian森林的分析（见“材料和方法”为细节）;狒狒被认为是最好的全祖征群。 “其他...” FORESTER的输出树文件（请参阅详细信息“材料和方法”），用于进一步的分析; （C）的分数0.00090的平均一致树导致从98个位点的类人猿（人科，灵长类动物，哺乳动物）的超级矩阵（见6.I的改性二进制表示导出的5339种树木的Hennigian森林的分析以及“材料和方法”的详细说明），但所有168棵，其中包含的分支（智人加PAN）已经从输入林中删除。 “其他...” FORESTER的输出树文件（参见“材料和方法”），用于进一步的分析。

On Star-Cover and Path-Cover of a Tree

摘要

著录项

相似文献

相关主题

期刊订阅