• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Southeastern International Conference on Combinatorics, Graph Theory and Computing; 20070305-09; Boca Raton,FL(US) >Graph Isomorphism Completeness for Perfect Graphs and Subclasses of Perfect Graphs
【24h】

Graph Isomorphism Completeness for Perfect Graphs and Subclasses of Perfect Graphs

机译：完美图和完美图子类的图同构完整性

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

摘要

A problem is said to be GI-complete if it is provably as hard as graph isomorphism; that is, there is a polynomial-time Turing reduction from the graph isomorphism problem. It is known that the GI problem is GI-complete for some special graph classes including regular graphs, bipartite graphs, chordal graphs and split graphs. In this paper, we prove that deciding isomorphism of double split graphs, the class of graphs exhibiting a 2-join, and the class of graphs exhibiting a balanced skew partition are GI-complete. Further, we show that the GI problem for the larger class including these graph classes-that is, the class of perfect graphs-is also GI-complete.
机译：如果一个问题与图同构一样困难，则认为该问题是GI完全的。也就是说，图同构问题存在多项式时间Turing约简。众所周知，对于某些特殊的图类，包括正则图，二部图，弦图和分裂图，GI问题是GI完全的。在本文中，我们证明了确定双分裂图的同构性，具有2个连接的图类和具有平衡的偏斜分区的图类是GI完全的。此外，我们表明，包括这些图类的较大类（即完美图的类）的GI问题也是GI完全的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号