...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The graph sandwich problem for 1-join composition is NP-complete
【24h】

The graph sandwich problem for 1-join composition is NP-complete

机译：1连接组成的图三明治问题为NP完全

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

摘要

A graph is a 1-join composition if its vertex set can be partitioned into four nonempty sets A_L, A_R, S_L and S_R such that: every vertex of A_L is adjacent to every vertex of A_R; no vertex of S_L is adjacent to vertex of A_R ∪ S_R; no vertex of S_R is adjacent to a vertex of A_L ∪ S_L. The graph sandwich problem for 1-join composition is defined as follows: Given a vertex set V, a forced edge set E~1, and a forbidden edge set E~3, is there a graph G = (V,E) such that E~1 is contained in E and E ∩ E~3 = 0, which is a 1-join composition graph? We prove that the graph sandwich problem for 1-join composition is NP-complete. This result stands in contrast to the case where S_L = 0 (S_R = 0), namely, the graph sandwich problem for homogeneous set, which has a polynomial-time solution.
机译：如果图的顶点集可以划分为四个非空集A_L，A_R，S_L和S_R，则该图为1联结组合：A_L的每个顶点与A_R的每个顶点相邻; S_L的顶点不与A_R∪S_R的顶点相邻;没有S_R的顶点与A_L∪S_L的顶点相邻。 1连接合成的图三明治问题定义如下：给定一个顶点集V，一个强制边集E〜1和一个禁止边集E〜3，则图G =（V，E）使得E〜1包含在E中，并且E∩E〜3 = 0，这是1连接组成图吗？我们证明1-连接组成的图三明治问题是NP完全的。该结果与S_L = 0（S_R = 0）（即齐次集的图三明治问题）具有多项式时间解的情况形成对比。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号