...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On decision and optimization (k, l)-graph sandwich problems
【24h】

On decision and optimization (k, l)-graph sandwich problems

机译：关于决策和最优化（k，l）-图三明治问题

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

摘要

A graph G is (k,l) if its vertex set can be partitioned into at most k independent sets and l cliques. The (k,l)-Graph Sandwich Problem asks, given two graphs G(1) = (V,E-1) and G(2) = (V,E-2), whether there exists a graph G = (V,E) such that E-1 subset of or equal to E subset of or equal to E-2 and G is (k,l). In this paper, we prove that the (k,l)-Graph Sandwich Problem is NP-complete for the cases k = 1 and l = 2; k = 2 and l = 1; or k = l = 2. This completely classifies the complexity of the (k,l)-Graph Sandwich Problem as follows: the problem is NP-complete, if k + l > 2; the problem is polynomial otherwise. We consider the degree Delta constraint subproblem and completely classify the problem as follows: the problem is polynomial, for k less than or equal to 2 or Delta less than or equal to 3; the problem is NP-complete otherwise. In addition, we propose two optimization versions of graph sandwich problem for a property II: MAX-II-GSP and MIN-II-GSP. We prove that MIN-(2, 1)-GSP is a Max-SNP-hard problem, i.e., there is a positive constant epsilon, such that the existence of an epsilon-approximative algorithm for MIN-(2, 1)-GSP implies P = NP. (C) 2004 Published by Elsevier B.V.
机译：如果图形G的顶点集最多可以划分为k个独立的集和l个集团，则它是（k，l）。 （k，l）-图三明治问题询问，给定两个图G（1）=（V，E-1）和G（2）=（V，E-2），是否存在图G =（V ，E），使得等于或等于E-2的E子集和等于E-2的E-1子集和G为（k，l）。在本文中，我们证明了在k = 1和l = 2的情况下（k，l）-图夹心问题是NP完全的; k = 2和l = 1;或k = l =2。这完全将（k，l）-Graph夹心问题的复杂度分类为：如果k + l> 2，则问题为NP完全问题;否则，为k-l。否则问题就是多项式。我们考虑度数Delta约束子问题，并将问题完全分类如下：对于k小于或等于2或Delta小于或等于3，问题是多项式。否则问题是NP完全的。此外，针对性质II，我们提出了图三明治问题的两个优化版本：MAX-II-GSP和MIN-II-GSP。我们证明MIN-（2，1）-GSP是一个Max-SNP-hard问题，即存在一个正常数epsilon，从而存在MIN-（2，1）-GSP的epsilon近似算法意味着P = NP。 （C）2004由Elsevier B.V.发布

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号