• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >WELL-COVERED CLAW-FREE GRAPHS
【24h】

WELL-COVERED CLAW-FREE GRAPHS

机译：覆盖覆盖的无爪图形

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

摘要

We prove the existence of a polynomial time algorithm to tell whether a graph, with no induced subgraph isomorphic to K-1.3 is well covered. A graph is well-covered if all its maximal independent sets are of the same cardinality. The problem is known to be polynomialy solvable where the input graph is a line graph and it is NP-hard for the larger family of all graphs which do not contain an induced subgraph isomorphic to K-1,K-4. (C) 1996 Academic Press, Inc. [References: 9]
机译：我们证明了多项式时间算法来判断图是否诱导的诱导子图对K-1.3产生很好的覆盖。 如果所有最大独立集都具有相同的基数，则图形是良好的。 已知该问题是多元素可溶性，其中输入图是线图，对于不含诱导的子目为K-1，K-4的所有曲线的较大家族，它是NP - 硬。 （c）1996年学术出版社，Inc。[参考文献：9]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号