• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >On the Complexity of Cover-Incomparability Graphs of Posets
【24h】

On the Complexity of Cover-Incomparability Graphs of Posets

机译：词组覆盖不可比图的复杂性

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

摘要

In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced subgraphs of C-I graphs of posets is polynomial.
机译：在本文中，我们证明了对姿势C-I图的识别问题是NP完全的。另一方面，我们证明了C-I图的诱导子图恰好是可比性图的补充，因此，姿势集C-I图的诱导子图的识别问题是多项式。

著录项

  • 来源
    《Order》 |2009年第3期|229-236|共8页
  • 作者

    Jana Maxova; Pavla Pavlikova; Daniel Turzik;

  • 作者单位

    Department of Mathematics, Institute of Chemical Technology, Prague, Technicka 5, 166 28 Praha 6, Czech Republic Institute for Theoretical Computer Science (ITI), Charles University, Malostranske nam. 25, 118 00 Praha 1, Czech Republic;

    Department of Mathematics, Institute of Chemical Technology, Prague, Technicka 5, 166 28 Praha 6, Czech Republic;

    Department of Mathematics, Institute of Chemical Technology, Prague, Technicka 5, 166 28 Praha 6, Czech Republic;

  • 收录信息 美国《科学引文索引》(SCI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    poset; graph; transitive orientation; NP-complete;

    机译：姿势图形;传递方向;NP完全;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号