...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The P versus NP-complete dichotomy of some challenging problems in graph theory
【24h】

The P versus NP-complete dichotomy of some challenging problems in graph theory

机译：图论中一些具有挑战性的问题的P与NP完全二分法

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

摘要

The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years.Among them is the central problem in theoretical computer science: the P versus NP problem, which aims to classify the possible existence of efficient solutions to combinatorial and optimization problems.The main goal is to determine whether there are questions whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.In this context, it is important to determine precisely what facet of a problem makes it NP-complete.We shall discuss classes of problems for which dichotomy results do exist: every problem in the class is classified into polynomial or NP-complete.We shall discuss our contribution through the classification of some long-standing problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes.More precisely, we have shown that Chvátal's skew partition is polynomial and that Roberts-Spencer's clique graph is NP-complete.We have also solved the dichotomy for Golumbic-Kaplan-Shamir's sandwich problem.We shall describe two examples where we can determine the full dichotomy: the edge-colouring problem for graphs with no cycle with a unique chord and the three nonempty part sandwich problem.Some open problems are discussed: the stubborn problem for list partition, the chromatic index of chordal graphs, and the recognition of split clique graphs.
机译：克莱数学研究所（Clay Mathematics Institute）选择了七个千年问题来激励人们研究多年来一直无法解决的重要经典问题，其中最重要的是理论计算机科学中的核心问题：P与NP问题，旨在对有效的可能存在进行分类组合和优化问题的解决方案。主要目标是确定是否存在可以快速检查答案的问题，但是通过任何直接步骤解决问题的时间都不可能很长。在这种情况下，准确确定哪个方面非常重要问题将使其成为NP完全的。我们将讨论确实存在二分法结果的问题类别：该类别中的每个问题都分为多项式或NP完全的。我们将通过对一些长期存在的问题的分类来讨论我们的贡献图论的重要领域：完美图，交集图和图类的结构表征更确切地说，我们已经证明了Chvátal的偏斜分区是多项式，而Roberts-Spencer的集团图是NP完全的。完全二分法：不具有唯一弦的无圈图的边缘着色问题和三个非空部分三明治问题。讨论了一些开放性问题：列表划分的顽固问题，弦图的色指数和拆分的识别集团图。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号