...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The complexity of dissociation set problems in graphs
【24h】

The complexity of dissociation set problems in graphs

机译：图中解离集问题的复杂性

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

摘要

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.
机译：如果图中一个顶点的子集诱导一个顶点度最大为1的子图，则称为分解集。最大分解集问题，即在给定图中找到最大尺寸的分解集的问题是已知的。对于二部图是NP难的。我们表明，对于平面二部图的平面线图，最大解离集问题是NP-困难的。此外，针对正在考虑的问题，我们描述了几种可多项式解决的情况。其中之一处理所谓的无椅子图的子类。此外，研究了在给定图中找到最大（包含）最小解的最大解集的相关问题，并得出了该问题（即弱弦和二分图）的NP硬度结果。最后，我们提供了上述解集问题的不可逼近结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号