...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On graph contractions and induced minors (Conference Paper)
【24h】

On graph contractions and induced minors (Conference Paper)

机译：关于图收缩和未成年人（会议论文）

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

摘要

The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in | ~(VH)| if G belongs to any nontrivial minor-closed graph class and H is a planar graph. For a fixed graph H, the H-Contractibility problem is to decide whether a graph can be contracted to H. The computational complexity classification of this problem is still open. So far, H has a dominating vertex in all cases known to be solvable in polynomial time, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete. We also present a new class of graphs H for which H-Contractibility can be solved in polynomial time. Finally, we study the (H,v)-Contractibility problem, where v is a vertex of H. The input of this problem is a graph G and an integer k, and the question is whether G is H-contractible such that the "bag" of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.
机译：诱导次要收容问题将两个图G和H作为输入，并询问G是否具有H作为诱导次要。我们证明这个问题是固定参数易处理的。 〜（VH）|如果G属于任何非平凡的次闭合图类，并且H是平面图。对于固定图H，H-可收缩性问题是确定是否可以将图收缩到H。此问题的计算复杂性分类仍然是开放的。到目前为止，H在所有已知可以在多项式时间内求解的情况下都具有一个支配的顶点，而H在所有已知为NP完全的情况下都没有这样的顶点。在这里，我们提出了一类具有主导顶点的图H，其可收缩性是NP完全的。我们还提出了一类新的图H，可以在多项式时间内求解H收缩性。最后，我们研究（H，v）-可收缩性问题，其中v是H的顶点。该问题的输入是图G和整数k，问题是G是否可H-可收缩，使得“对应于v的G的“ bag”至少包含k个顶点。我们证明，无论何时连接H且v不是H的主要顶点，此问题都是NP完全的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号