Finding induced trees

N. Derhy; C. Picouleau

首页> 外文期刊>Discrete Applied Mathematics >Finding induced trees

【24h】

Finding induced trees

机译：寻找诱导树

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

Let G = (V(G), E(G)) be a finite connected undirected graph and W V(G)a subsetof vertices. We are searching for a subset X V(G) such that W X and the subgraphinduced on X is a tree. N P-completeness results and polynomial time algorithms are givenassuming that the cardinality of W is fixed or not. Besides we give complexity results whenX has to induce a path or when G is a weighted graph. We also consider problems wherethe cardinality of X has to be minimized

机译：令G =（V（G），E（G））是有限连接的无向图，而W V（G）是顶点的子集。我们正在搜索子集X V（G），使得W X和在X上诱导的子图是一棵树。假设W的基数固定或不固定，则给出N个P-完备性结果和多项式时间算法。此外，当X必须归纳路径或G是加权图时，我们给出复杂度结果。我们还考虑了必须最小化X的基数的问题

著录项

来源
《Discrete Applied Mathematics》 |2009年第17期|共6页
作者
N. Derhy; C. Picouleau;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Induced subgraph; Induced tree; NY-completeness; Polynomial time algorithm;

机译：诱导子图诱导树NY完备性多项式时间算法;

相似文献

外文文献
中文文献
专利

1. Finding induced trees [J] . N. Derhy, C. Picouleau Discrete Applied Mathematics . 2009,第17期

机译：寻找诱导树
2. A two-stages tree-searching algorithm for finding three completely independent spanning trees [J] . Pai Kung-Jui, Chang Ruay-Shiung, Wu Ro-Yu, Theoretical computer science . 2019,第期

机译：一种双级树搜索算法，用于查找完全独立的跨越树
3. Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees [J] . Atsuko Yamaguchi, Kiyoko F. Aoki, Hiroshi Mamitsuka Information Processing Letters . 2004,第2期

机译：查找部分k树的最大公共子图和具有生成树的多项式有界数的图
4. Finding a path is harder than finding a tree [C] . Christopher Meek International workshop on Artificial Intellignece and Statistics . 2001

机译：寻找一条路径比找到树更难
5. Design and implementation of parallel graph algorithms for minimum spanning tree, list ranking, and root finding on trees. [D] . Chung, Sun Bong. 1998

机译：并行图算法的设计和实现，用于最小生成树，列表排序和树的根查找。
6. Finding the tree of life: matching phylogenetic trees to the fossil record through the 20th century. [O] . M. J. Benton 2001

机译：寻找生命之树：将系统发育树与20世纪的化石记录相匹配。
7. PCITMiner- Prefix-based Closed Induced Tree Miner for finding closed induced frequent subtrees [O] . Kutty Sangeetha, Nayak Richi, Li Yuefeng 2007

机译：基于PCITMiner-Prefix的封闭式诱导树挖掘器，用于查找封闭式诱导频繁子树
8. Science Findings, Issue 107. Growing Trees Where Trees Grow Best: Short-Term Research Sheds Light on Long-Term Productivity [R] . Harrington, C., Terry, T., Harrison, R. 2008

机译：科学研究结果，第107期。树木成长最佳的树木：短期研究为长期生产力提供支持

Finding induced trees

摘要

著录项

相似文献

相关主题

期刊订阅