...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion
【24h】

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

机译：证明NP-Hard假设的多项式算法意味着NP-hard的结论

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

摘要

A number of results in hamiltonian graph theory are of the form "P_1 implies P_2", where P_1 is a property of graphs that is NP-hard and P_2 is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvatal-Erdos Theorem, which states that every graph G with α ≤ k is hamiltonian. Here k is the vertex connectivity of G and α is the cardinality of a largest set of independent vertices of G. In another paper Chvatal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than k independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.
机译：汉密尔顿图论中的许多结果的形式为“ P_1表示P_2”，其中P_1是具有NP-hard的图的属性，而P_2是也是NP-hard的图的循环结构。这种定理的一个示例是众所周知的Chvatal-Erdos定理，该定理指出，每个α≤k的图G都是哈密顿量。这里k是G的顶点连通性，α是G的最大独立顶点集的基数。在另一篇论文中，Chvatal指出，该结果的证明实际上是多项式时间构造，该构造会产生汉密尔顿循环或a多于k个独立顶点的集合。在本文中，我们指出了哈密顿图论中的其他定理具有相似的特征。特别是，我们给出了关于16个或更多顶点上的图的荣格定理（Ann。Discrete Math。3（1978）129）的构造证明。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号